AT_abc395_d [ABC395D] Pigeon Swap

有 $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 \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 完成