#6548. 「CERC2018」The Bridge on the River Kawaii

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 CERC 2018B. 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

样例

样例输入 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
-1
3
-1
3
4
3
-1

样例输入 2

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

样例输出 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