405028 - 农场看守

农场看守的工作就是巡视农场并且保证没有坏人破坏农场,农场看守从谷仓出发去巡视,并且最终回到谷仓。负责任的农场看守需要对农场的每一条连接不同场地的路走两遍以发现是不是有异常情况,并且这两边必须是不同的方向(同一条路径要按照相反的方向各走一遍)。 现在的题目是:保证每块地之间一定会由至少一条路相连,请帮负责任的农场看守制定巡视路线。前提假设一定存在满足题意的路径。

输入

第一行输入两个数N(2≤N≤10 000)和M(1≤M≤50 000),表示农场一共有N块地M条路。 第二到M+1行输入两个整数,表示对应的两块地之间有一条路。

输出

输出为2×(M+1)行,每行一个数字,表示农场看守的巡查路径上地的编号,1号为谷仓,从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号地,依此类推。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题