农场看守

Grade 100 Open Time Wednesday, 17 June 2020, 9:40 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:40 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:40 PM
Input file watchcow.in Output file watchcow.out

【题目描述】农场看守(watchcow)USACO 2005 January Silver

农场看守的工作就是巡视农场并且保证没有坏人破坏农场,农场看守从谷仓出发去巡视,并且最终回到谷仓。负责任的农场看守需要对农场的每一条连接不同场地的路走两遍以发现是不是有异常情况,并且这两边必须是不同的方向(同一条路径要按照相反的方向各走一遍)。

现在的题目是:保证每块地之间一定会由至少一条路相连,请帮负责任的农场看守制定巡视路线。前提假设一定存在满足题意的路径。

【输入格式】

第一行输入两个数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号地,依此类推。