巡逻母牛(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

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

样例输出 #1

1
4
3
4
2
3
2
4
1
2
1

数据范围

请使用高效率算法及 64 位整数（long long）避免溢出。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接