You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

A. 小车串串

题目描述

给定 $N$ 个小车，每个小车的编号分别为：$1, 2, \dots, N$。

现在有 $Q$ 个操作，每个操作执行以下 3 种操作之一：

• -1 x y：将 $x$ 和 $y$ 相连（$y$ 在 $x$ 之后）
• -2 x y：将 $x$ 和 $y$ 的连接解除
• -3 x：输出 $x$ 所在链的长度，及其这条链中的所有元素（从前往后）

输入格式

第一行输入两个整数 $N, Q$，分别表示小车数量和操作数量。 接下来 $Q$ 行，每行输入一个操作，格式为上述三种之一。

输出格式

对于每个询问 -3 x，输出一行答案： 第一个数是链的长度 $p$，接下来 $p$ 个数为链上的小车编号（从前往后）。

样例

输入样例#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 < N < 10^5$
• $1 \le Q \le 10^5$
• $1 < x < N$
• $1 \le y \le N$
• 输入均为整数
• 第三种操作的输出元素总和不超过 $10^6$ 个