Problem1274--双向链表练习题

1274: 双向链表练习题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 23  Solved: 6
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有 n 个线性表 L1,L2,…,LnL_1, L_2, \dots, L_nL1,L2,,Ln.
初始时,LiL_iLi 仅包含元素 i, 即 Li=[i]L_i = [i]Li=[i].
他依次执行了 m 次操作。第 i 次操作由两个整数 ai,bia_i, b_iai,bi 指定, 每次操作分为两步:
1. Lai←reverse(Lai+Lbi)L_{a_i} \leftarrow \mathrm{reverse}(L_{a_i} + L_{b_i})Laireverse(Lai+Lbi), 其中 ←\leftarrow 表示赋值,+ 表示列表的连接,reverse\mathrm{reverse}reverse 表示列表的反转。例如,reverse([1,2]+[3,4,5])=[5,4,3,2,1]\mathrm{reverse}([1, 2] + [3, 4, 5]) = [5, 4, 3, 2, 1]reverse([1,2]+[3,4,5])=[5,4,3,2,1].
2. Lbi←[]L_{b_i} \leftarrow []Lbi[]. 其中 [] 表示空的列表。
输出 m 次操作后, L1L_1L1 的元素。

Input

多组输入。
第一行包含两个整数 n 和 m.
接下来 m 行,其中第 i 行包含 2 个整数ai,bi
1<=n,m<=100000
1<=ai,bi<=n,ai!=bi

Output

先输出L1的长度 ,再输出|L1|个整数,表示L1的元素。

Sample Input

3 3
3 2
3 2
1 3

Sample Output

3 2 3 1

HINT

注:此题不面向初试数据结构。

Source/Category