AT_abc225_d.[ABC225D] Play Train

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

高桥君正在用玩具火车进行连接和分离的游戏。
共有 $N$ 辆火车，分别命名为火车 $1$ 、火车 $2$ 、 $\ldots$ 、火车 $N$ 。
一开始，所有火车都是分开的，互不连接。

现在有 $Q$ 个操作，请按给定顺序依次处理。
操作有以下 $3$ 种类型之一：

1 x y ：将火车 $x$ $x$ 的尾部与火车 $y$ $y$ 的头部连接。
保证以下条件成立：
- $x \neq y$
- 在执行该操作前，火车 $x$ 的尾部没有连接其他火车
- 在执行该操作前，火车 $y$ 的头部没有连接其他火车
- 在执行该操作前，火车 $x$ 和火车 $y$ 属于不同的连通分量
2 x y ：将火车 $x$ $x$ 的尾部与火车 $y$ $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

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

处理到 $\mathrm{query}_5$ 时，火车的连接情况如下图所示。此时，例如火车 $2$ 与火车 $3,5,6,7$ 属于同一连通分量，但与火车 $1,4$ 不属于同一连通分量。

处理到 $\mathrm{query}_{11}$ 时，火车的连接情况如下图所示。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?