The Bridge on the River Kawaii
Time limit5sMemory limit512 MB
Maintain a graph under bridge insertions and deletions, and for each query answer the minimum possible maximum edge weight on a path between two islands, where weights are single digits.
- Level
Hard9 of 10
- Topics
- Dynamic programming, Union-find, Graph, Divide and conquer
- Solved
- No attempts yet
Problem
In a very distant land called Midsommer there is a cute little river delta. Deep purple acid flows in the river, so swimming there is impossible. Several islands lie in the delta, and bridges connect some pairs of them. Every bridge has a danger level, which measures how dangerous it is to travel across that bridge; higher levels are more dangerous.
A detective who is also, by coincidence, a mystery novelist, Richard Hradecki often has to travel between the islands to pursue his cases. Among all possible paths he prefers the safest one, meaning the highest danger level of a bridge on the path must be as low as possible.
For planning purposes Richard usually asks you to find the safest path from one island to another island where he is investigating. To handle his requests you have to keep registering three types of events:
- A new bridge between two islands was just built by members of a local tribe.
- A big pink fluffy acid bear named Lug appears and destroys a bridge.
- Richard asks you to find the safest path between two islands.
Input
The first line of input contains two integers N and Q (2 ≤ N ≤ 105 and 1 ≤ Q ≤ 105). N is the number of islands, labeled 0, 1, ..., N − 1, and Q is the number of events that follow.
Each of the next Q lines represents one event and contains three or four integers, interpreted as follows:
- 0 X Y V : A bridge of danger level V (0 ≤ V < 10) was just built between islands X and Y.
- 1 X Y : The bridge connecting islands X and Y was just destroyed.
- 2 X Y : Richard asks what the safest path from island X to island Y is.
For every type of event, X and Y denote a valid pair of islands (0 ≤ X, Y < N and X ≠ Y). There is always at most one bridge between any pair of islands. A bridge to be destroyed always exists at that moment.
Output
For each event of type 2, output a line with the danger level of the most dangerous bridge on the safest path from X to Y. If there is no path between X and Y, output −1.