分数: 350 点
问题陈述
有 N 鸽子标记 1, 2, \ldots, N 和 N 巢标记 1, 2, \ldots, N.
最初,鸽子 i (1 \leq i \leq N) 在巢中 i.
您将执行 Q 对这些鸽子进行操作。
操作分为三种类型:
- 类型 1:给你整数 a 和 b (1 \leq a \leq N, 1 \leq b \leq N)。拿鸽子 a 移出当前嵌套并将其移至嵌套 b.
- 类型 2:给你整数 a 和 b (1 \leq a < b \leq N)。将所有鸽子移入巢中 a 筑巢 b,并移动巢中的所有鸽子 b 筑巢 a。这两个动作同时发生。
- 类型 3:给你一个整数 a (1 \leq a \leq N)。鸽子 a 报告它当前所在的巢的标签。
打印每个类型的结果 3 按照给出的操作顺序进行操作。
约束
- 1 \leq N \leq 10^6
- 1 \leq Q \leq 3 \times 10^5
- 每个操作都是类型 1, 2,或 3.
- 根据问题陈述所有操作均有效。
- 至少有一种类型 3 操作。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q op _ 1 op _ 2 \vdots op _ Q
在这里, op _ i 上线 i+1 代表 i采用以下格式之一的第次操作。
如果 i-th 操作的类型 1, op _ i 的格式如下:
1 a b
这对应于类型 1 给定整数的运算为 a 和 b.
如果 i-th 操作的类型 2, op _ i 的格式如下:
2 a b
这对应于类型 2 给定整数的运算为 a 和 b.
如果 i-th 操作的类型 3, op _ i 的格式如下:
3 a
这对应于类型 3 给定整数的运算为 a.
输出
让类型的数量 3 操作是 q。打印 q 行。的 i第行 (1 \leq i \leq q) 应包含报告中报告的巢号 i-第类型 3 操作。
样本输入 1
6 8 1 2 4 1 3 6 3 2 2 4 5 3 2 1 4 2 3 4 3 2
示例输出 1
4 5 2 5
在给定的操作中,鸽子的移动如下图所示:

为该类型报告的嵌套编号 3 操作是 4,5,2,5。打印 4, 5, 2, 5 在单独的行上。
示例输入 2
1 2 1 1 1 3 1
示例输出 2
1
类型的目标嵌套 1 操作可能与鸽子当前所在的巢穴相同。
示例输入 3
30 15 3 3 2 8 30 2 12 15 2 2 17 1 19 1 2 7 30 3 12 3 8 2 25 26 1 13 10 1 16 10 2 16 29 2 1 21 2 6 11 1 21 8
示例输出 3
3 15 7