题目描述

有 $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 的操作的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $Q$
$op_1$
$op_2$
$\vdots$
$op_Q$

其中，第 $i+1$ 行的 $op_i$ 表示第 $i$ 次操作，格式为以下之一：

• 若为类型 1 操作：
  1 a b
  表示以 $a$ 和 $b$ 为参数执行类型 1 操作。

• 若为类型 2 操作：
  2 a b
  表示以 $a$ 和 $b$ 为参数执行类型 2 操作。

• 若为类型 3 操作：
  3 a
  表示以 $a$ 为参数执行类型 3 操作。

输出格式

设类型 3 的操作共有 $q$ 个，输出 $q$ 行，每行对应一个类型 3 操作的查询结果（即鸽子所在巢的编号）。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

1 2
1 1 1
3 1

输出 #2

1

输入输出样例 #3

输入 #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

说明/提示

约束条件

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 3 \times 10^5$
• 所有操作均符合题目描述中的参数范围。
• 输入中至少包含一个类型 3 操作。
• 输入均为整数。

样例解释 1

操作过程中鸽子的移动如图所示（图片链接略）。类型 3 操作应报告的巢编号依次为 $4,5,2,5$，因此输出四行：4、5、2、5。

样例解释 2

在类型 1 操作中，可能存在将鸽子取出后又放回原巢的情况。

翻译由 DeepSeek R1 完成

---

AtCoder 原题连接 {{ select(1) }}

• 写完了
• 还没写完