The Bridge on the River Kawaii#9748
In a distant land called Midsommer, there lies a charming little river delta. The river flows with deep purple acid, making it impossible to swim. Scattered throughout the delta are several islands, some of which are connected by bridges. Each bridge has a danger level assigned to it, where a higher value indicates a more dangerous crossing.
A detective — and, coincidentally, a mystery novelist — named Richard Hradecki frequently travels between the islands while working on his investigations. Among all possible routes, Richard prefers the safest path, defined as the path where the highest danger level among the bridges used is as low as possible.
To help Richard with his travels, you must continuously handle three types of events:
A new bridge is built between two islands by members of a local tribe.
A giant, pink, fluffy acid bear named Lug appears and destroys a bridge.
Richard asks for the safest route between two islands.
The first line contains two integers and q~(2 \le n \le 10^5, 1 \le q \le 10^5) — the number of islands and the number of events, respectively. The islands are labeled from to n - 1.
Each of the next lines represents an event and contains either three or four integers, interpreted as follows:
0~x~y~v: A bridge of danger level v~(0 \le v < 10) is built between islands and .
: The bridge between islands and is destroyed.
: Richard asks for the safest path between islands and .
For all events:
and y~(0 \le x, y < n, x \ne y) are valid and distinct island indices.
There is at most one bridge between any pair of islands at any time.
Any bridge scheduled for destruction exists at the moment of removal.
For each query of type , print a single line with the danger level of the most dangerous bridge on the safest path from island to island . If there is no path between them, print .
Example 1
Example 2