Problem H. Eulerian cycle

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of vertex numbers, connected by some edge. There is at most one edge connecting two vertices.

Output file format

Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle. If there does not exist any Eiler cycle, output file must contain 1.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

0.038s 0.010s 15