4227：张老师的玩具车
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：24
解决：0
题目描述
## 题目描述
张老师正在玩一套可以自由拆装的模型玩具车。
共有 $N$ 节车厢，编号为 $1,2,\ldots,N$，起初全部彼此独立，没有任何连接关系。
张老师会按顺序执行 $Q$ 次操作，每次操作会改变这些车厢的连接方式，或要求你查询某节车厢所在的整列玩具车。
所有操作都满足题中描述的合法性条件。
现在有 $Q$ 个操作，请按给定顺序依次处理。
操作有以下 $3$ 种类型之一：
- `1 x y` ：将玩具车 $x$ 的尾部与玩具车 $y$ 的头部连接。
保证以下条件成立：
- $x \neq y$
- 在执行该操作前，玩具车 $x$ 的尾部没有连接其他玩具车
- 在执行该操作前，玩具车 $y$ 的头部没有连接其他玩具车
- 在执行该操作前，玩具车 $x$ 和玩具车 $y$ 属于不同的连通分量
- `2 x y` ：将玩具车 $x$ 的尾部与玩具车 $y$ 的头部分离。
保证以下条件成立：
- $x \neq y$
- 在执行该操作前，玩具车 $x$ 的尾部与玩具车 $y$ 的头部直接连接
- `3 x` ：输出包含玩具车 $x$ 的连通分量中所有玩具车的编号，**按从头到尾的顺序**输出。
## 输入格式
输入通过标准输入给出，格式如下：
> $N$ $Q$
> $\mathrm{query}_1$
> $\mathrm{query}_2$
> $\vdots$
> $\mathrm{query}_Q$
第 $i$ 个操作 $\mathrm{query}_i$，首先给出操作类型 $c_i$（$1,2,3$ 之一）。
若 $c_i=1,2$，则还会给出 $x,y$；若 $c_i=3$，则还会给出 $x$。
即，每个操作有以下三种格式之一：
> $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$
设 $c_i=3$ 类型的操作共有 $q$ 个，请输出 $q$ 行。
第 $k$ 行输出第 $k$ 个此类操作的答案。
## 输入输出样例 #1
### 输入 #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
```
## 说明/提示
### 数据范围
- $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$
### 样例解释 1
处理到 $\mathrm{query}_5$ 时，玩具车的连接情况如下图所示。此时，例如玩具车 $2$ 与玩具车 $3,5,6,7$ 属于同一连通分量，但与玩具车 $1,4$ 不属于同一连通分量。
处理到 $\mathrm{query}_{11}$ 时，玩具车的连接情况如下图所示。
