1079 : 双向链表练习题

Description

Bobo 有 n 个列表 L₁, L₂, …, L_n. 初始时，L_i 仅包含元素 i, 即 L_i = [i]. 他依次执行了 m 次操作。第 i 次操作由两个整数 a_i, b_i 指定, 每次操作分为两步：

1. L_ai ← reverse(L_ai + L_bi), 其中 ← 表示赋值，+ 表示列表的连接，reverse 表示列表的反转。例如，reverse([1, 2] + [3, 4, 5]) = [5, 4, 3, 2, 1].
2. L_bi ← []. 其中 [] 表示空的列表。

输出 m 次操作后， L₁ 的元素。

Input

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含两个整数 n 和 m.

接下来 m 行，其中第 i 行包含 2 个整数 a_i, b_i.

• 1 ≤ n, m ≤ 10⁵
• 1 ≤ a_i, b_i ≤ n, a_i ≠ b_i
• n 的总和，m 的总和都不超过 5 × 10⁵.

Output

对于每组数据，先输出 L₁ 的长度 |L₁|，再输出 |L₁| 个整数，表示 L₁ 的元素。

Sample

2 1
1 2
2 1
2 1
3 3
3 2
3 2
1 3

2 2 1
0
3 2 3 1

Hint

Source

Author

ftiasch