Description

Translated from [CERC2018] The Bridge on the River Kawaii.

In a faraway place called Midsommer, there is a small river named delta, and you cannot swim in it. Around the river there are some small islands, and bridges connect some pairs of islands. Each bridge has a danger value, which indicates how dangerous it is to cross that bridge. The higher the danger value, the more dangerous it is to cross.

A detective and mystery novelist named Richard Hradecki needs to cross these bridges while investigating cases. For each investigation, among all possible paths, he chooses the safest one: the path whose maximum bridge danger value along the path is as small as possible.

In each investigation, Richard travels from one island to another island he wants to investigate. You need to help him find the safest path. Meanwhile, the set of existing bridges can change. Specifically, you need to handle the following three types of events:

• Locals build a new bridge between two islands.
• An acidic, furry, big pink bear named Lug destroys a bridge.
• Richard asks for the safest route between two islands.

Input Format

The first line contains two integers $N,Q$. $N$ is the number of islands (islands are numbered $0 \ldots N-1$), and $Q$ is the number of events to process.

The next $Q$ lines each describe an event, containing three or four integers as follows (it is guaranteed that $X,Y$ are two distinct valid islands):

• 0 X Y V: build a bridge with danger value $V$ between islands $X$ and $Y$.
• 1 X Y: the bridge connecting islands $X$ and $Y$ is destroyed.
• 2 X Y: Richard asks for the safest path from $X$ to $Y$.

It is guaranteed that between any two islands there is at most one direct bridge, and every bridge to be destroyed exists before it is destroyed (i.e., the input is valid).

Output Format

For each event of type $2$, output the danger value of the most dangerous bridge on the safest path from $X$ to $Y$. If there is no path between $X$ and $Y$, output $-1$.

6 15
0 1 2 1
2 1 4
2 1 5
0 2 3 2
2 1 4
2 1 5
0 3 4 3
2 1 4
2 1 5
0 4 5 4
2 1 4
2 1 5
1 4 5
2 1 4
2 1 5

-1
-1
-1
-1
3
-1
3
4
3
-1

6 6
0 2 0 4
0 3 4 3
0 0 4 1
0 2 5 4
2 3 2
2 4 2

4
4

Hint

Constraints: $2\le N\le 10^5,1\le Q\le 10^5,0\le V< 10,0\le X,Y<N,X\neq Y$.

Translated by ChatGPT 5