# 50111. Hamiltonian Cycle

## I'm a slow walker, but I never walk backwards.

Write a program to find a cycle in a network of cities.

We are given a set of cities (indexed from 0 to $N - 1$) and roads in which a road connects two cities. You need to find a cycle of roads that visits each city exactly once. There could be many solutions so you need to output the cycle with the least dictionary order. If there is no such cycle, output “NO SOLUTION”.

Let us illustrate the task with an examples. There are five cities and seven roads as in the following figure. Both $0-1-2-3-4-0$ and $0-1-4-3-2-0$ are cycles that go through each city exactly once, but we need to output $0-1-2-3-4-0$ as the solution because it has smallest dictionary order.

sample

• Each city has exactly two roads: 20 points.
• There are exactly five cities: 20 points.
• General case: 60 points.

## Input Format

There are two numbers $N$ and $E$ in the first line. $N$ is the number of cities and $E$ is the number of roads. The next $E$ lines are roads and each road contains city $x$ and city $y$.

• $0 \lt N \lt 1001$
• $0 \lt E \lt 150000$

## Output Format

Print the Hamiltonian cycle by the vertex index in one line.

## Sample Input 1

1234565 50 11 22 33 44 0


## Sample Output 1

10 1 2 3 4 0


## Sample Input 2

123456785 70 11 22 33 44 01 40 2


## Sample Output 2

10 1 2 3 4 0


## Sample Input 3

12345678910117 103 01 03 24 14 25 25 35 46 16 5


## Sample Output 3

10 1 6 5 4 2 3 0