Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2018
The Bridge on the River Kawaii
bridge.c, bridge.cpp, Bridge.java, bridge.py
In a very distant land called Midsommer, there is a cute little river delta. Deep purple acid
flows in the river, so it is impossible to swim there. There are several islands in the delta and
bridges connecting some pairs of them. Every bridge is assigned a danger level, which measures
how dangerous it is to travel across that bridge, higher levels being more dangerous.
A detective, and as matter of coincidence also a mystery novels author, Richard Hradecki often
needs to travel between the islands to pursue his detective cases. Among all possible paths, he
prefers to choose the safest one, which means 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 him the safest path from one island
to another island where he is investigating. To be able to satisfy his requests, you have to
continuously register 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 Lug appears and destroys a bridge.
· Richard asks you to find the safest path between two islands.
Input Specification
The first line of input contains two integers N and Q (2 ≤ N ≤ 105 and 1 ≤ Q ≤ 105). N is the
number of islands (which are labeled 0, 1, . . . , N - 1) and Q is the number of events to follow.
Each of the next Q lines represents one event and it contains three or four integers, interpreted
as follows:
· 0 X Y V : A bridge of danger level V (0 ≤ V < 10) has just been built between islands X
and Y .
· 1 X Y : The bridge connecting islands X and Y has just been destroyed.
· 2 X Y : Richard asks what is the safest path from island X to island Y .
For all types of events, 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 Specification
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.
Sample Input 1
Output for Sample Input 1
6
15
-1
0
12
1
-1
2
14
-1
2
15
-1
0
23
2
3
2
14
-1
2
15
3
0
34
3
4
2
14
3
2
15
-1
0
45
4
2
14
2
15
1
45
2
14
2
15
Sample Input 2
Output for Sample Input 2
6
6
4
0
2
0
4
4
0
3
4
3
0
0
4
1
0
2
5
4
2
3
2
2
4
2
