Description

Farmer John has $N$ farms ($2 \leq N \leq 10^4$). These farms are connected by $M$ roads ($1 \leq M \leq 5 \times 10^4$). Multiple edges may exist.

Bessie starts patrolling from farm $1$. Each road must be traversed exactly once in each direction, and finally she must return to farm $1$.

Please output one path that satisfies the requirements above.

It is guaranteed that such a path exists. If there are multiple valid paths, output any one of them.

Input Format

The first line contains two integers $N, M$.

The next $M$ lines each contain two integers $u, v$, describing a road between $u$ and $v$.

Output Format

Output the farms visited, one per line.

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

1
2
3
4
2
1
4
3
2
4
1

Hint

Translated by ChatGPT 5