盒子与球

题目描述

有编号为 $1,2,\ldots,N$ 的 $N$ 个盒子,以及编号为 $1,2,\dots,10^{100}$ 的 $10^{100}$ 个球。

初始时,盒子 $i$ 中只装有球 $i$。

接下来要处理一共 $Q$ 次操作。

操作共有三种类型:$1$、$2$ 和 $3$。

类型 $1$:把盒子 $Y$ 中的全部内容物放入盒子 $X$。保证 $X \neq Y$。

1 X Y

类型 $2$:把球 $k+1$ 放入盒子 $X$,其中 $k$ 是当前盒子中所装球的总数。

2 X

类型 $3$:输出装有球 $X$ 的盒子编号。

3 X

输入格式

输入按以下格式从标准输入给出。

这里,$op_i$ 表示第 $i$ 次操作。

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

输出格式

对于每次类型 $3$ 的操作,输出一行,包含作为回答的整数。

样例

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

5
4
3
1
3

该输入包含十次操作。

第 $1$ 次操作是类型 $3$。球 $5$ 在盒子 $5$ 中。

第 $2$ 次操作是类型 $1$。把盒子 $4$ 中的全部内容物放入盒子 $1$。

现在盒子 $1$ 装有球 $1$ 和 $4$,盒子 $4$ 为空。

第 $3$ 次操作是类型 $2$。把球 $6$ 放入盒子 $1$。

第 $4$ 次操作是类型 $2$。把球 $7$ 放入盒子 $4$。

第 $5$ 次操作是类型 $3$。球 $7$ 在盒子 $4$ 中。

第 $6$ 次操作是类型 $1$。把盒子 $1$ 中的全部内容物放入盒子 $3$。

现在盒子 $3$ 装有球 $1$、$3$、$4$、$6$,盒子 $1$ 为空。

第 $7$ 次操作是类型 $3$。球 $4$ 在盒子 $3$ 中。

第 $8$ 次操作是类型 $1$。把盒子 $4$ 中的全部内容物放入盒子 $1$。

现在盒子 $1$ 装有球 $7$,盒子 $4$ 为空。

第 $9$ 次操作是类型 $3$。球 $7$ 在盒子 $1$ 中。

第 $10$ 次操作是类型 $3$。球 $6$ 在盒子 $3$ 中。

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• 对于每次类型 $1$ 的操作,$1 \le X,Y \le N$ 且 $X \neq Y$。
• 对于每次类型 $2$ 的操作,$1 \le X \le N$。
• 对于每次类型 $3$ 的操作,当时球 $X$ 在某个盒子中。
• 至少有一次类型 $3$ 的操作。