P15049 [UOI 2022 II Stage] 图 2

双倍经验：

给定一个包含 $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$)。

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

### 评分细则 - （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 完成