This article is based on the official editorial.

The original problem is reducible to the following subproblem:

There is an undirected, connected graph with \(N\) vertices and \(M\) edges. Each edge is assigned a positive integer weight. Process \(Q\) queries in the following format:

• Given distinct vertices \(u, v\), find the maximum value of \(x\) such that there exists a path from \(u\) to \(v\) consisting of only edges with weight no less than \(x\).

Assuming \(M=O(N)\), the official editorial presents an offline algorithm that utilizes parallel binary search with time complexity \(O(N\log N+(N+Q)\alpha(N)\log\max F_{i,j})\). It can also be solved in \(O((N+Q)\alpha(N)\log N)\) time with coordinate compression.

Here, we present an online algorithm using partially persistent DSU, a data structure that supports the following operations:

• \(\mathtt{initialize}(n)\): Initializes an undirected graph \(G\) with \(n\) vertices and \(0\) edges.
  • Time complexity: \(O(n)\)
• \(\mathtt{merge}(u, v)\): Adds an edge connecting vertices \(u\) and \(v\) in \(G\).
  • Time complexity: \(O(\log n)\)
• \(\mathtt{same}(u, v, t)\): Determines whether vertices \(u\) and \(v\) are connected in \(G\) after the first \(t\) \(\mathtt{merge}\) operations.
  • Time complexity: \(O(\log n)\)

The following resource contains information on the implementation details of partially persistent DSU:

• https://codeforces.com/blog/entry/119919 (Problem 2)

Using partially persistent DSU, the following solution runs in \(O(N\log N+Q\log^2 N)\) time:

1. Sort the \(M\) edges in descending order of weight, and let the sorted sequence be \((e_1, \dots, e_M)\).
2. Initialize a graph with \(N\) vertices, and perform the \(\mathtt{merge}\) operation \(M\) times. Here, the \(i\)-th operation adds edge \(e_i\) to the graph.
3. For each query, use binary search to find the minimum \(t\) such that \(\mathtt{same}(u, v, t)\) is true, and output the weight of \(e_t\).

Alternatively, we may omit binary search by directly maintaining the DSU tree in step 2 and finding the LCA of \(u, v\) for each query in step 3. Since this can be implemented with standard DSU and a sparse table, we obtain a solution with time complexity \(O(N\log N+Q)\).