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.
Each city has exactly two roads: 20 points.
There are exactly five cities: 20 points.
General case: 60 points.
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$
Print the Hamiltonian cycle by the vertex index in one line.