题目描述

译自 CERC 2018「B. The Bridge on the River Kawaii」

在一个遥远的，叫做 Midsommer 的地方，有一条叫做 delta 的小河。河里流的是深紫色的酸，所以不可能在那里游泳。这条河周围有一些小岛，并且有桥连接它们。每座桥都有一个危险系数，表示通过这座桥有多危险。危险系数越高，通过这座桥就越危险。

一位叫做 Richard Hradecki 的侦探兼悬疑小说作家经常需要通过这些桥来追查案件。在所有可能的路径中，他更倾向于选择最安全的一条，也就是这条路径上经过桥的最大危险系数越低越好。

为了规划路线，Richard 经常让你为他找从一个岛到他要调查的岛的最安全路线。为了满足他的需求，你需要连续处理以下三种事件：

• 当地人在两座岛屿之间建了一座新桥；
• 一只酸性的并且毛茸茸的大粉熊 Lug 出现了，并摧毁了一座桥；
• Richard 要求你找两个岛屿之间的最安全路线。

输入格式

第一行包含两个整数 $N,Q$。$N$ 是岛屿数（岛屿用 $0\ldots N-1$ 标号），$Q$ 是需要处理的事件数。

接下来 $Q$ 行，每行表示一个事件，包含三或四个整数，说明如下：

• $0\ X\ Y\ V$：在 $X$ 岛与 $Y$ 岛之间刚建成一座危险系数为 $V$ 的桥；
• $1\ X\ Y$：连接 $X,Y$ 两岛的桥刚被摧毁；
• $2\ X \ Y$：Richard 询问从 $X$ 到 $Y$ 的最安全路径。

对于所有类型的询问，$X,Y$ 表示一对合法的岛屿。保证任意两个岛屿之间最多只存在一座直达的桥，要被摧毁的桥在那一刻是存在的。

输出格式

对于每个种类为 $2$ 的事件，输出 $X$ 到 $Y$ 最安全路径上经过的最危险的桥的危险系数。如果 $X$ 与 $Y$ 之间没有路径，输出 $-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

数据范围与提示

$2\le N\le 10^5,1\le Q\le 10^5,0\le V\lt 10,0\le X,Y\lt N,X\neq Y$