[ABC372] E - K-th Largest Connected Components

E - K-th Largest Connected Components

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 475 分

题面

有一个包含 个顶点和 条边的无向图。顶点编号从 到 。

你将会处理 个按顺序进行的查询。每个查询包含以下两种类型之一：

• 类型 ：以 1 u v 的格式给出。在顶点 和 之间添加一条边。
• 类型 ：以 2 v k 的格式给出。输出与顶点 相连的顶点中第 大的顶点编号。如果与顶点 相连的顶点少于 个，则输出 -1。

限制条件

• 在类型 的查询中，。
• 在类型 的查询中，，。
• 所有输入值均为整数。

---

输入

以下是标准输入给出的格式：

这里， 是第 个查询，可以按以下格式给出：

输出

设 为类型 的查询次数。输出 行，第 行包含第 个类型 查询的答案。

---

输入样例 1

4 10
1 1 2
2 1 1
2 1 2
2 1 3
1 1 3
1 2 3
1 3 4
2 1 1
2 1 3
2 1 5

输出样例 1

2
1
-1
4
2
-1

• 第一个查询中，添加了顶点 和 之间的边。
• 第二个查询中，顶点 连接了两个顶点： 和 。其中，第 大的顶点编号是 ，应输出。
• 第三个查询中，顶点 连接了两个顶点： 和 。其中，第 大的顶点编号是 ，应输出。
• 第四个查询中，顶点 连接了两个顶点： 和 ，少于 个，所以输出 -1。
• 第五个查询中，添加了顶点 和 之间的边。
• 第六个查询中，添加了顶点 和 之间的边。
• 第七个查询中，添加了顶点 和 之间的边。
• 第八个查询中，顶点 连接了四个顶点：。其中，第 大的顶点编号是 ，应输出。
• 第九个查询中，顶点 连接了四个顶点：。其中，第 大的顶点编号是 ，应输出。
• 第十个查询中，顶点 连接了四个顶点：，少于 个，所以输出 -1。

---

输入样例 2

6 20
1 3 4
1 3 5
2 1 1
2 3 1
1 1 5
2 6 9
2 1 3
2 6 1
1 4 6
2 2 1
2 6 2
2 4 7
1 1 4
2 6 2
2 3 4
1 2 5
2 4 1
1 1 6
2 3 3
2 1 3

输出样例 2

1
5
-1
3
6
2
5
-1
5
3
6
4
4