Processing math: 100%

Problem C. 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

1N,M100000

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.050s 0.008s 13