Description

If a graph can be traversed with a single stroke (without lifting the pen), the path of such a traversal is called an Eulerian trail. If the path starts and ends at the same vertex, it is called an Eulerian circuit.
According to the two theorems of Eulerian paths, to find an Eulerian circuit, perform a depth-first traversal (DFS) starting from any vertex.
To find an Eulerian trail, perform DFS starting from a vertex with an odd degree. The time complexity is O(m + n), where m is the number of edges and n is the number of vertices.

Input Format

The first line contains n and m, representing n vertices and m edges. The following m lines describe the pairs of vertices connected by each edge.

Output Format

Output an Eulerian trail or Eulerian circuit, presenting a valid path.

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

1 5 4 3 2 1