iff

problem

There are $N$ propositions, named $1, 2, \ cdots, N$, respectively. Also, $M$ information about the propositions is given. The $i$ th information is "$a_i$$". Given in the form "b_i$", which means that $a_i$ is $b_i$. ("If" is a logical conditional and the transition law holds.) $For each proposition$ i $ Output all propositions that have the same value as i $ in ascending order. However, proposition $i$ and proposition $i$ are always the same value. Proposition $X$ and proposition $Y$ have the same value as "$if$ X $". It means "Y$" and "$X$ if $Y$".

output

On the $i$ line, output all propositions that have the same value as the proposition $i$, separated by blanks in ascending order. Also, output a line break at the end of each line.

Example

Input

5 2 1 2 2 1

Output

1 2 1 2 3 4 5

inputFormat

outputFormat

Output all propositions that have the same value as i $in ascending order. However, proposition$ i $and proposition$ i $are always the same value. Proposition$ X $and proposition$ Y $have the same value as "$ if $X$". It means "Y $" and "$ X $if$ Y $".

output

On the $i$ line, output all propositions that have the same value as the proposition $i$, separated by blanks in ascending order. Also, output a line break at the end of each line.

Example

Input

5 2 1 2 2 1

Output

1 2 1 2 3 4 5

样例

5 2
1 2
2 1

1 2
1 2
3
4
5

</p>