AT_abc225_d [ABC225D] Play Train

高桥君正在用玩具火车进行连接和分离的游戏。 共有 $N$ 辆火车，分别命名为火车 $1$、火车 $2$、$\ldots$、火车 $N$。 一开始，所有火车都是分开的，互不连接。 现在有 $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$ 个此类操作的答案。

### 数据范围 - $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}$ 时，火车的连接情况如下图所示。  由 ChatGPT 4.1 翻译