Problem Description

There are $N$ stacks, numbered from $1$ to $N$. Initially, the $i$-th stack only contains a number $i$. Now there are $M$ move operations, and the $i$-th operation is to move all the numbers in stack $a_i$ to stack $b_i$. Specifically speaking, we pop all the numbers in stack $a_i$ one by one, and push them to stack $b_i$ in the order of popping (the first to be popped is the first to be pushed).

After all the $M$ operations, you should output the numbers in the stacks.

Input

There are multiple test cases.

For each test case, the first line contains $2$ integers $N$ and $M$ $(1\leq M \leq N \leq 10^5)$.

In the next $M$ lines, each line contains $2$ integers $a_i$ and $b_i$ $(1\leq a,b \leq N, ~ a\neq b)$, denoting an operation.

It's guaranteed that the sum of $N$ of all the test cases is no more than $2 \cdot 10^5$.

Output

For each test case, print $n$ lines. The $i$-th line begins with an integer $S_i$, denoting the number of numbers in the $i$-th stack, followed by $S_i$ integers, denoting the numbers in the $i$-th stack from top to bottom.

6 5
1 2
2 3
3 4
4 5
6 2

0
1 6
0
0
5 4 2 1 3 5
0