玩具火车

题目描述

高桥君正在玩玩具火车,将它们连接或断开。

有 $N$ 节玩具火车车厢,车厢编号为:1 号车厢、2 号车厢、……、$N$ 号车厢。

初始时,所有车厢都是分离的。

接下来给出 $Q$ 个查询,请按给出的顺序依次处理。查询共有三种类型,如下所示。

1 x y:将 $y$ 号车厢的车头连接到 $x$ 号车厢的车尾。

保证满足:

• $x \neq y$
• 执行该查询前,$x$ 号车厢的车尾没有连接任何车厢
• 执行该查询前,$y$ 号车厢的车头没有连接任何车厢
• 执行该查询前,$x$ 号车厢和 $y$ 号车厢属于不同的连通分量

2 x y:将 $y$ 号车厢的车头从 $x$ 号车厢的车尾断开。

保证满足:

• $x \neq y$
• 执行该查询前,$y$ 号车厢的车头直接连接在 $x$ 号车厢的车尾上

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$

输出应包含 $q$ 行,其中 $q$ 是 $c_i = 3$ 的查询个数。

第 $k$ 行($1 \le k \le q$)应输出对第 $k$ 个此类查询的响应。

样例

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

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$ 个查询时车厢的状态。

例如,车厢 $2$ 与车厢 $3, 5, 6, 7$ 属于同一连通分量,该分量与包含车厢 $1, 4$ 的连通分量不同。

下图显示了处理前 $11$ 个查询时车厢的状态。

数据范围

• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le x \le N$
• $1 \le y \le N$
• 输入中的所有值均为整数。
• 所有查询都满足题目描述中列出的条件。
• 所有 $3 x$ 格式的查询要求输出的车厢编号总数至多为 $10^6$。