← 返回题目列表

AtCoder · abc395_d

G. 鸽子交换

中文机器翻译题面 查看原题

分数: 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