题目描述

贝西（Bessie）被任命为农场的新巡逻奶牛。每天晚上，她的任务是穿过农场，确保没有坏人做坏事。她从牛棚（编号为 $1$ 的场地）出发，完成巡逻后返回牛棚。

如果她是一头更敏锐的奶牛，她可能只需要走过农场上的 $M$（$1 \leq M \leq 50,000$）条双向小径（编号 $1..M$）各一次，就能确保她已经检查了一切。但由于她不够敏锐，她希望确保每条小径恰好走两次，并且两次行走的方向相反，以避免重复遗漏相同的事物。

注意，两个场地之间可能由多条小径连接。请找到一条满足贝西要求的路径。题目保证这样的路径存在。

输入格式

• 第 $1$ 行：两个整数 $N$（场地数量，$2 \leq N \leq 10,000$）和 $M$（小径数量）。
• 第 $2$ 行到第 $M+1$ 行：每行两个整数，表示一条连接两个场地的小径。

输出格式

• 第 $1$ 行到第 $2M+1$ 行：每行一个整数，表示贝西经过的场地编号。路径必须从牛棚（$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

提示

输出解释：
贝西从牛棚 $1$ 出发，依次经过 $2, 3, 4, 2, 1, 4, 3, 2, 4$，最后返回 $1$。每条小径均被正反方向各走一次。

题目来源

USACO 2005 January Silver