int getRoot(int u) {
  if (u == dsu[u]) return u;
  return dsu[u] = getRoot(dsu[u]);
}

void addEdge(int u, int v) {
  u = getRoot(u); v = getRoot(v);

  dsu[n] = n;
  dsu[u] = dsu[v] = n;

  adj[n].push_back(u);
  if (u != v) adj[n].push_back(v);

  ++n;
}

void build() {
  for (int i = 0; i < n; ++i) dsu[i] = i;
  for (int i = 0; i < m; ++i) addEdge(U[i], V[i]);
}

We will build a reachability tree while processing the queries backward so that deletion of an edge can be seen as addition of an edge. Whenever we process a query of the second type, add this edge to the reachability tree (by creating a new node and attach to the roots of the two connecting vertices). When processing a query of the first type, we store the current root of this vertex, which we will answer later on.

After the reachability tree is built, we process the queries again (this time in forward order). We can now answer the queries of the first type as a subtree-maximum query, while you can skip the query of the second type. Do an Eulerian tour on our reachability tree so that each subtree can be represented as a segment, then we can use a segment tree to process all our queries.

If the queries can be processed offline, then this problem can be solved using parallel binary search.

Let's solve the online version. First, observe that two people can switch places if and only if they are in the same connected component, and either the component they are in contains a vertex with degree at least $$$3$$$ or the component contains a cycle. We say a connected component to be switchable if any two people from two different vertices from this connected component can switch places.

We will build a reachability tree by adding the edges from the smallest weight to the largest weight. After adding an edge, check whether the connected component where the newly added edge is in is switchable. If it is switchable, mark this newly added node in the reachability tree as switchable.

When given a query with vertices $$$X$$$ and $$$Y$$$, find the LCA of these two nodes in the reachability tree. From the LCA, find the nearest ancestor (possibly the LCA itself) that is switchable, then the weight of the edge corresponding to this node will be the answer to this query. All of these can be done with the help of sparse tables.

We will build two reachability trees. We will focus on the method of building one of the trees, the other one can be done similarly.

Unlike the usual reachability tree where we add edges, we will add the vertices in descending order of indices. The reachability tree starts with $$$N$$$ nodes representing the original vertices, then whenever we add a vertex, add a new node to the tree, then consider all the neighbours that have been added so far. For each of these neighbours, find its root in the current reachability tree. All these roots will then be attached as the children of the newly added node. From the resulting tree so far, for all queries with $$$L$$$ equal to the currently added vertex number, find the root of $$$S$$$. This means the set of reachable vertices from $$$S$$$ and $$$\le L$$$ can be represented as a subtree of this root node.

Perform DFS, then we can order the leaves of the reachability tree according to their preorder numbering. Hence, each subtree can now be represented as a segment $$$[x_l, x_r]$$$.

The other reachability tree for reachable vertices from $$$E$$$ and $$$\ge R$$$ can be built similarly by adding vertices in ascending order of indices.

To answer the query, we can check whether the two segments have a number that intersects. Unfortunately, we cannot simply intersect ranges as a vertex can have different preorder numbering in both trees. Let the preorder numbering of a vertex from both trees be $$$x$$$ and $$$y$$$, then we can represent this vertex as a point $$$(x, y)$$$ on a two-dimensional plane. In this scenario, our query can now be answered by querying whether there exists a point in the rectangle $$$[x_l, x_r] \times [y_l, y_r]$$$, where $$$[x_l, x_r]$$$ and $$$[y_l, y_r]$$$ are the ranges represented by the corresponding subtrees of this query. This checking can be done using segment tree.