USACO Training 3.3.1 Riding the Fences 题解

农民 John 每年需要处理大量栅栏的修复工作。他通常会骑着马逐一穿过所有栅栏，并对破损部位进行修补。John 与其他农民一样，有着懒惰的性格特征。他对骑马这项活动并不感兴趣，因此从不会重复经过任何一个栅栏。现在需要编写一个程序，读取关于栅栏网络的信息，并设计出一条路径，使得每条栅栏恰好被经过一次。John 可以从任意一个顶点（即两个栅栏交汇的点）出发，也可以在任意一个顶点结束行程。

每条栅栏连接两个顶点，这些顶点编号从1到500（尽管某些农场可能并未使用全部编号）。一个顶点可以连接多个（至少为1个）栅栏。所有栅栏构成的整体是连通的（即可以从任意一条栅栏抵达其他所有栅栏）。

程序需输出 John 骑马所经过的路径，具体表现为依次访问的顶点编号序列。如果存在多种可行解，则按照500进制数的规则选择最小的那个（即优先考虑第一个数字较小的情况；若仍有多个解，则比较第二个数字，依此类推）。输入数据确保至少存在一种可行解。

PROGRAM NAME: fence
INPUT FORMAT
第 1 行: 一个整数 F(1 <= F <= 1024)，表示总共有多少条栅栏
第 2 到 F+1 行: 每行包含两个整数 i, j(1 <= i,j <= 500)，表示某条栅栏连接的是i号和j号顶点。

SAMPLE INPUT(fence.in)
9
1 2
2 3