CSG-CPC Online Judge

1079 : 双向链表练习题

         Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 131     Solved: 43    

Description

Bobo 有 n 个列表 L1, L2, …, Ln. 初始时,Li 仅包含元素 i, 即 Li = [i]. 他依次执行了 m 次操作。第 i 次操作由两个整数 ai, bi 指定, 每次操作分为两步:

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

输出 m 次操作后, L1 的元素。

Input

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

每组数据的第一行包含两个整数 nm.

接下来 m 行,其中第 i 行包含 2 个整数 ai, bi.

  • 1 ≤ n, m ≤ 105
  • 1 ≤ ai, bi ≤ n, ai ≠ bi
  • n 的总和,m 的总和都不超过 5 × 105.

Output

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

Sample Input

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

Sample Output

2 2 1
0
3 2 3 1

Hint

Author

ftiasch