题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

1
2
3
4
2
1
4
3
2
4
1

提示

输出详细信息：

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