0x60图论（0x66 Tarjan算法与无向图连通性）例题4：看牛

P6066 [USACO05JAN] Watchcow S

题目描述

每条边正反各走一边的欧拉回路

Farmer John 有 $N$ 个农场（$2 \leq N \leq 10^4$），这些农场由 $M$ 条道路连接（$1 \leq M \leq 5 \times 10^4$）。不保证没有重边。

Bassie 从 $1$ 号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到 $1$ 号农场。

请输出一条满足上述要求的路径。

保证这样的路径存在。如果有多条路径，任意输出一条即可。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行两个整数 $u,v$，描述一条 $u$ 到 $v$ 的道路。

输出格式

输出经过的农场，一行一个。

输入输出样例 #1

输入 #1

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

输出 #1

1
2
3
4
2
1
4
3
2
4
1