EIU Programming Practices and Exams

Mr. A assigned Mr. B the task of writing a program to print the signs for the game "Finding the Treasure", information about signboards including the names of the places where the boards are to be placed and the names of the areas to go. However, after receiving the result, Mr. A discovers a bug in Mr. B's program so that the result contains a series of signs that, after following the signs, players will return to the original position (Example: a to b , b to c, c to a). Mr. A wants to write a software to prove it. Note that the game will start at location 0.

Input

The first line contains 2 positive integers n, m (n, m ≤ 10 ^ 5) which are the number of places and the number of signboards that Mr. B has printed.

For the next m lines, each line is a signpost, including the name of the place and the place to go, separated by a space.

Each location is numbered from 0 to n-1.

Output

Output the cycle. Note that all testcases which have cycles, have one cycle contains place 0.

Example:

Input

4 5

3 1

0 1

1 2

3 0

2 0

Output

0 1 2

More e.g.

3 3
0 2
2 1
1 0