Bobo has $n$ lists $L_1, L_2, \dots, L_n$. Initially, $L_i$ contains only the element $i$, i.e., $L_i = [i]$. He performs $m$ operations in sequence. The $i$-th operation is specified by two integers $a_i, b_i$, and each operation consists of two steps:

1. $L_{a_i} \leftarrow \mathrm{reverse}(L_{a_i} + L_{b_i})$, where $\leftarrow$ denotes assignment, $+$ denotes list concatenation, and $\mathrm{reverse}$ denotes list reversal. For example, $\mathrm{reverse}([1, 2] + [3, 4, 5]) = [5, 4, 3, 2, 1]$.
2. $L_{b_i} \leftarrow []$, where $[]$ denotes an empty list.

Output the elements of $L_1$ after $m$ operations.

Input

The input contains multiple test cases. Process until the end of the file.

The first line of each test case contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $a_i, b_i$.

• $1 \leq n, m \leq 10^5$
• $1 \leq a_i, b_i \leq n, a_i \neq b_i$
• The sum of $n$ and the sum of $m$ over all test cases do not exceed $5 \times 10^5$.

Output

For each test case, first output the length of $L_1$, denoted as $|L_1|$, followed by $|L_1|$ integers representing the elements of $L_1$.

Examples

Input 1

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

Output 1

2 2 1
0
3 2 3 1