题目背景

双倍经验：https://www.luogu.com.cn/problem/P5064

题目描述

给定一个包含 $n$ 个顶点的图。同时给出 $q$ 个三种类型的查询：

• 在顶点 $v_i$ 所在的连通分量中，需要找到编号第 $k_i$ 小的顶点编号。如果不存在，则返回 $-1$。顶点 $v_i$ 所在的连通分量是指所有可以通过边从顶点 $v_i$ 到达的顶点集合。
• 向图中添加一条连接顶点 $u_i$ 和 $v_i$ 的边。
• 返回到执行完第 $x_i$ 次操作后的状态。

请找出所有第一类查询的答案。

输入格式

第一行包含三个整数 $n$、$q$、$g$ ($1 \leq n, q \leq 5 \cdot 10^5$, $0 \leq g \leq 9$)。

接下来的每一行描述一个查询：

• 第一类查询：$v_i$、$k_i$ ($1 \leq v_i, k_i \leq n$)。
• 第二类查询：$v_i$、$u_i$ ($1 \leq v_i, u_i \leq n$)。
• 第三类查询：$x_i$ ($0 \leq x_i < i$)。

输出格式

对于每个第一类查询，输出该查询的答案。

10 12 0
1 1 1
2 1 2
2 1 6
2 9 10
2 3 10
2 10 6
1 1 5
1 1 3
3 5
1 1 3
3 0
1 1 3

1
9
3
6
-1

10 17 0
2 1 2
1 2 2
2 3 4
1 3 2
2 6 7
2 7 8
1 7 2
1 7 3
2 5 6
1 5 5
1 5 4
2 5 4
2 3 2
1 1 7
1 1 4
1 1 8
1 1 9

2
4
7
8
-1
8
7
4
8
-1

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

3
6
1
2
-1
6
5

5 5 0
2 1 2
1 1 2
3 0
2 1 3
1 1 2

2
3

提示

评分细则

• （6 分）： $n, q \leq 100$；没有第二类和第三类操作。
• （7 分）： $n, q \leq 100$；没有第三类操作。
• （4 分）： $n, q \leq 100$。
• （9 分）： $n, q \leq 3 \cdot 10^5$；保证在第二类操作中 $|v_i - u_i| = 1$；没有第三类查询。
• （8 分）： $n, q \leq 3 \cdot 10^5$，没有第三类查询。
• （10 分）： $n, q \leq 3 \cdot 10^5$；保证在第二类操作中 $|v_i - u_i| = 1$。
• （19 分）： $n, q \leq 10^5$。
• （17 分）： $n, q \leq 3 \cdot 10^5$。
• （20 分）： 无额外限制。

翻译由 DeepSeek V3 完成