#P14924. [uoi2022-2s-day2]哥萨克武斯与图

    ID: 14140 传统题 6000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500数据结构并查集分块DFS可持久化线段树搜索

[uoi2022-2s-day2]哥萨克武斯与图

题目描述

给定一个有 nn 个顶点的图。接下来有 qq 次询问,询问共有三种类型:

  1. 在顶点 viv_i 所在的连通块中,找到编号第 kik_i 小的顶点编号。如果不存在这样的顶点,则返回 −1-1。顶点 viv_i 所在的连通块,指所有可以从 viv_i 沿图中的边到达的顶点组成的集合。
  2. 向图中加入一条连接顶点 uiu_i 和 viv_i 的边。
  3. 回到执行完 xix_i 次操作之后的图的状态。

请输出所有第一类询问的答案。

输入格式

第一行包含三个整数 n,q,gn,q,g,其中 1≤n,q≤5×1051 \le n,q \le 5 \times 10^5,0≤g≤90 \le g \le 9。

接下来 qq 行,每行描述一次询问。询问格式如下:

  • 第一类询问:1 v_i k_i,其中 1≤vi,ki≤n1 \le v_i,k_i \le n;
  • 第二类询问:2 v_i u_i,其中 1≤vi,ui≤n1 \le v_i,u_i \le n;
  • 第三类询问:3 x_i,其中 0≤xi<i0 \le x_i < i。

这里第 ii 次操作中的 xix_i 表示回到“已经执行完 xix_i 次操作之后”的状态。特别地,xi=0x_i=0 表示回到初始状态。

输出格式

对于每个第一类询问,输出一行一个整数,表示该询问的答案。

样例 1

输入

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

样例 2

输入

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

样例 3

输入

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

样例 4

输入

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

输出

2
3

评分方式

  1. 66 分:n,q≤100n,q \le 100,没有第二类和第三类操作。
  2. 77 分:n,q≤100n,q \le 100,没有第三类操作。
  3. 44 分:n,q≤100n,q \le 100。
  4. 99 分:n,q≤3×105n,q \le 3 \times 10^5,保证所有第二类操作中 ∣vi−ui∣=1|v_i-u_i|=1,且没有第三类询问。
  5. 88 分:n,q≤3×105n,q \le 3 \times 10^5,没有第三类询问。
  6. 1010 分:n,q≤3×105n,q \le 3 \times 10^5,保证所有第二类操作中 ∣vi−ui∣=1|v_i-u_i|=1。
  7. 1919 分:n,q≤105n,q \le 10^5。
  8. 1717 分:n,q≤3×105n,q \le 3 \times 10^5。
  9. 2020 分:无额外限制。