1015. The Worst Stretch on Every Route

A map has n places and m two-way roads. Road i joins u and v and has roughness w. A route is judged by its WORST road, not by the total: the roughness of a route is the largest roughness among the roads it uses.

For each of q questions s t, print the smallest roughness any route from s to t can have. Print 0 when s equals t, since a route of no roads has no worst road, and print -1 when no route exists at all.

``` 4 places, roads 1-2 (5), 2-3 (5), 1-3 (9), 3-4 (2)

1 to 3 -> 5 going through 2 beats the direct road of 9 1 to 4 -> 5 the same two roads, then the quiet one 2 to 2 -> 0 ```

``` 5 places, roads 1-2 (1), 2-3 (100), 3-4 (1), 4-5 (1)

1 to 5 -> 100 every route has to cross the bad road 4 to 5 -> 1 ```

## What most people try first

Per question, binary search the roughness and test each candidate with a traversal over the roads within the limit. That is O((n + m) log W) per question, so at q = 2000 and m = 5000 it is roughly 2 * 10^8 steps with a large constant, and it repeats the same work for every question.

A shortest-path algorithm is a worse fit still. Its whole argument rests on costs adding up along a route, and here they do not: one more quiet road costs nothing at all, so a long detour is often better than a short scramble.

## Add the roads in order and watch who joins

Sort the roads by roughness and add them one at a time. The moment s and t land in the same group, the road just added is the answer for that question: every road used so far is at most that rough, and no set of quieter roads joined them.

sort the roads by roughness pending = every question with s != t for each road (w, u, v) in increasing w: if the union actually merged: for each pending question (s, t): if find(s) == find(t): answer it w and drop it from pending answers not filled in are -1

Rescanning the pending list only after a road that MERGED something matters: a road whose ends were already together cannot change any answer, and skipping the rescan there is what keeps the sweep honest.

## Why the first moment is the right answer

Adding roads in increasing roughness means that after processing every road of roughness at most W, two places share a group exactly when some route between them uses only roads that rough. So the first roughness at which s and t share a group is the smallest W for which such a route exists, which is the definition of the answer.

## The two answers that are not a road

s equal to t answers 0 and must be taken out before the sweep, because the two are in the same group from the very start and would otherwise be answered by the first road that merges anything.

A question whose two places are never joined answers -1, and that is simply what is left after the sweep finishes.

## Cost, and what a bigger version would need

The sweep rescans the pending list after every merge, so the total is O(m q alpha(n)), about 10^7 at these limits, which is why n, m and q here are in the thousands rather than the hundreds of thousands. A version at those larger sizes would build a Kruskal reconstruction tree and answer each question by a lowest-common-ancestor query, which is a genuinely different piece of machinery and is not what this problem is for.

## Overflow

Roughness reaches 10^9, which fits in a signed 32 bit integer whose maximum is 2147483647. Nothing is ever added, so no 64 bit type is needed anywhere.

## Cross-reference

Problem 1645 asks this for the single pair 1 and n and can stop the sweep the moment those two meet. Problem 794 asks the opposite direction, whether a given limit is enough, which lets it sort the QUESTIONS instead of rescanning them.

## Cost

Time O(m log m + m q alpha(n)). Space O(n + m + q).

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ m ≤ 5000` - `1 ≤ q ≤ 2000` - `1 ≤ u, v, s, t ≤ n` - `1 ≤ w ≤ 1000000000` - The same pair may be joined by more than one road.