AI翻译，公式、数字等可能存在问题，如果存在问题，请点击上面查看英文版

分数：400分

问题描述

高山正在玩玩具火车，连接和断开它们。

有$N$辆玩具火车车厢，编号为：Car $1$，Car $2$，$\ldots$，Car $N$。

最初，所有的车厢都是分开的。

你将会得到$Q$个查询。按照给定的顺序处理它们。查询有三种类型，如下所述。

• 1 x y：将Car $y$的前部连接到Car $x$的后部。

保证满足以下条件：

• $x eq y$

• 在此查询之前，没有火车连接到Car $x$的后部；

• 在此查询之前，没有火车连接到Car $y$的前部；

• 在此查询之前，Car $x$和Car $y$属于不同的连通分量。

• 2 x y：将Car $y$的前部从Car $x$的后部断开。

保证满足以下条件：

• $x eq y$；

• 在此查询之前，Car $y$的前部直接连接到Car $x$的后部。

• 3 x：打印属于包含Car $x$的连通分量的车厢编号，从前到后。

约束条件

• $2 \leq N \leq 10^5$

• $1 \leq Q \leq 10^5$

• $1 \leq x \leq N$

• $1 leq y \leq N$

• 输入中的所有值都是整数。

• 所有查询都满足问题描述中的条件。

• 格式为3 x的查询总共要求打印最多$10^6$个车厢编号。

---

输入

输入从标准输入以以下格式给出：

$N$ $Q$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

第$i$个查询$\mathrm{query}\_i$以一个整数$c_i$（$1$，$2$或$3$）开头，表示查询的类型，后面跟着$x$和$y$（如果$c\_i = 1$或$2$），以及$x$（如果$c_i = 3$）。

简而言之，每个查询都是以下三种格式之一：

$1$ $x$ $y$

$2$ $x$ $y$

$3$ $x$

输出

如果一个查询带有$c\_i = 3$要求打印值$j\_1, j\_2, \ldots, j\_M$，则输出以下行：

$M$ $j_1$ $j_2$ $\ldots$ $j_M$

你的输出应包含$q$行，其中$q$是查询带有$c\_i = 3$的数量。

第$k$行（$1 \leq k \leq q$）应包含对第$k$个此类查询的响应。

---

样本输入1

7 14

1 6 3

1 4 1

1 5 2

1 2 7

1 3 5

3 2

3 4

3 6

2 3 5

2 4 1

1 1 5

3 2

3 4

3 6

---

样本输出1

5 6 3 5 2 7

2 4 1

5 6 3 5 2 7

4 1 5 2 7

1 4

2 6 3

下图显示了处理前5个查询时的车厢情况。

例如，Car $2$与Cars $3, 5, 6, 7$属于同一个连通分量，这与包含Cars $1, 4$的连通分量不同。

下图显示了处理前11个查询时的车厢情况。