题目描述

贝西被任命为农场的新守望者。每天晚上，她的工作是穿过农场，确保没有作恶的人在做任何坏事。她从谷仓开始，巡逻，完成后返回谷仓。如果她是一头更细心的奶牛，她也许可以在编号为$\red{1.. }$ $\red{N (2 <= N <= 10,000) }$个字段之间行走编号为 $\red{1..M }$的 $\red{M (1 <= M <= 50,000) }$条双向路径。

$\red{N }$在农场上一次，并确信她已经看到了她需要看到的一切。但既然她不是，她想确保她在每条小径上准确走两次。同样重要的是，她沿着每条小径的两次旅行方向相反，这样她就不会错过同样的事情两次。一对字段可能由多个路径连接。找到一条 $\red{Bessie }$可以遵循的满足她要求的路径。这样的路径保证存在。

约翰有$\red{N(2≤}$$\red{N≤}$$\red{10000)}$个农场，它们由$\red{M(1≤}$$\red{M≤}$$\red{50000)}$条双向路连接．贝茜从农场$\red{1}$出发去巡逻．每条路必须由两个方向各走一遍，最后回到农场$\red{1}$．题目保证这样的路径存在．请输出这样的路径．

输入格式

第$\red{1}$行输入$\red{N，}$$\red{M}$;

之后$\red{M}$行输入一条路的两个端点．

输出格式

第$\red{1...2M+1}$行：她通过的字段列表，每行一个，以字段$\red{1}$的仓库开始和结束。如果可能有多个解决方案，则输出任何解决方案。

样例

输入样例

4 5//四个点,五条边
1 2
1 4
2 3
2 4
3 4

输出样例

1
2
3
4
2
1
4
3
2
4
1

提示

输出详细信息：

贝西从（$\red{1}$谷仓）开始，到$\red{2，}$然后到$\red{3，}$等等