题目描述

译自 [CERC2018] The Bridge on the River Kawaii

在遥远的 Midsommer ，有一条叫 delta 的小河，河里无法游泳。这条河周围有一些小岛，小岛之间有桥连接。每座桥都有一个危险系数，表示通过这座桥有多危险。危险系数越高，通过这座桥就越危险。

一位叫做 Richard Hradecki 的侦探兼悬疑小说作家追查案件时需要经过这些桥。每次追查案件，他会在所有可能的路径中选择最安全的一条，也就是经过桥的最大危险系数最低的一条路径。

每次调查案件时，Richard 会从一个岛屿前往要调查的岛屿。他希望你帮他找到最安全的路径。同时，桥的存在情况也会变化。具体的，你需要处理以下三种事件：

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

输入格式

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

接下来 $Q$ 行，每行表示一个事件，包含三或四个整数，说明如下（保证 $X,Y$ 为两个不相同的合法的岛屿）：

• 0 X Y V：在 $X$ 岛与 $Y$ 岛之间建成一座危险系数为 $V$ 的桥；
• 1 X Y：连接 $X,Y$ 两岛的桥被摧毁；
• 2 X Y：Richard 询问从 $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\le 10,0\le X,Y<N,X\neq Y$