Drawing in One Stroke

Problem Background

Special for beginners, ^_^

Problem Description

If a graph admits a one-stroke drawing, the path of that drawing is called an Euler trail; if it also returns to the starting point at the end, the path is called an Euler circuit.

We call a vertex odd if the number of edges incident to it is odd. For graphs that can be drawn in one stroke, we have the following two theorems.

Theorem 1: A graph has an Euler trail if and only if it is connected and has exactly $2$ odd-degree vertices.

Theorem 2: A graph has an Euler circuit if and only if it is connected and has $0$ odd-degree vertices.

The correctness of the two theorems is obvious: since every edge must be traversed exactly once, for an Euler trail, every vertex other than the start and the end must be entered exactly as many times as it is left, so it is clearly even-degree; for an Euler circuit, every vertex is entered and left the same number of times, so there is clearly no odd-degree vertex.

The algorithm to find an Euler trail is simple: just use a depth-first traversal.

According to the two theorems, to find an Euler circuit, run a depth-first traversal from any vertex; to find an Euler trail, run a DFS from an odd-degree vertex. 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, m$, meaning there are $n$ vertices and $m$ edges. The following $m$ lines describe the two endpoints of each edge. The graph is guaranteed to be a connected simple graph, i.e. there are no multiple edges between any two vertices. $1 \le n, m \le 1000$.

Output Format

Output a path. Print the vertices in lexicographically smallest order, separated by a single space, forming an Euler trail or an Euler circuit. The data guarantees that a trail or a circuit always exists.

Sample Input

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

Sample Output

1 2 3 4 5 1

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.