P7457 [CERC2018] The Bridge on the River Kawaii

**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/)[ The Bridge on the River Kawaii](https://contest.felk.cvut.cz/18cerc/solved/bridge.pdf)** 在遥远的 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$。

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