Hamiltonian Cycle

[littlehug]

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

Task Description

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.

figure

Subtask

• 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.

  Output Format

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

  Sample Input 1

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

  Sample Output 1

  0 1 2 3 4 0

  Sample Input 2

  5 7
  0 1
  1 2
  2 3
  3 4
  4 0
  1 4
  0 2

  Sample Output 2

  0 1 2 3 4 0