102253: [AtCoder]ABC225 D - Play Train

Problem Statement

Takahashi is playing with toy trains, connecting and disconnecting them.
There are $N$ toy train cars, with car numbers: Car $1$, Car $2$, $\ldots$, Car $N$.
Initially, all cars are separated.

You will be given $Q$ queries. Process them in the order they are given. There are three kinds of queries, as follows.

• 1 x y: Connect the front of Car $y$ to the rear of Car $x$.
  It is guaranteed that:

  • $x \neq y$
  • just before this query, no train is connected to the rear of Car $x$;
  • just before this query, no train is connected to the front of Car $y$;
  • just before this query, Car $x$ and Car $y$ belong to different connected components.

• 2 x y: Disconnect the front of Car $y$ from the rear of Car $x$.
  It is guaranteed that:

  • $x \neq y$;
  • just before this query, the front of Car $y$ is directly connected to the rear of Car $x$.

• 3 x: Print the car numbers of the cars belonging to the connected component containing Car $x$, from front to back.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq x \leq N$
• $1 \leq y \leq N$
• All values in input are integers.
• All queries satisfy the conditions in the Problem Statement.
• The queries of the format 3 x ask to print at most $10^6$ car numbers in total.

Input

Input is given from Standard Input in the following format:

$N$ $Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

The $i$-th query $\mathrm{query}_i$ begins with an integer $c_i$ ($1$, $2$, or $3$) representing the kind of the query, followed by $x$ and $y$ if $c_i = 1$ or $2$, and followed by $x$ if $c_i = 3$.

In short, each query is in one of the following three formats:

$1$ $x$ $y$

$2$ $x$ $y$

$3$ $x$

Output

If a query with $c_i = 3$ asks to print the values $j_1, j_2, \ldots, j_M$, output the following line:

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

Your output should consist of $q$ lines, where $q$ is the number of queries with $c_i = 3$.
The $k$-th line $(1 \leq k \leq q)$ should contain the response to the $k$-th such query.

Sample Input 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

Sample Output 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

The figure below shows the cars when the first $5$ queries are processed.
For example, Car $2$ belongs to the same connected component as Cars $3, 5, 6, 7$, which is different from the connected component containing Cars $1, 4$.

The figure below shows the cars when the first $11$ queries are processed.

问题描述

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

有$N$辆玩具火车车厢，车号分别为：车$1$，车$2$，$\ldots$，车$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$的连通分量中的车厢编号。

限制条件

• $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$）开头，表示查询的类型，如果$c_i = 1$或$2$，后面跟着$x$和$y$，如果$c_i = 3$，后面跟着$x$。

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

$1$ $x$ $y$

$2$ $x$ $y$

$3$ $x$

输出

如果格式为$3 x$的查询要求打印值$j_1, j_2, \ldots, j_M$，输出以下行：

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

你的输出应由$q$行组成，其中$q$是格式为$3 x$的查询的数量。
第$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$个查询时的车厢状态。
例如，车$2$属于与车$3, 5, 6, 7$相同的连通分量，而与车$1, 4$所在的连通分量不同。

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