1692: 公路巡逻
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：66
Solved：20
Description
大保是一名公路保安员，常年巡逻在云贵山区的公路上。云贵山区共有n条公路，将山区的每一个村镇都连通起来了。村镇用1到800来编号，每个村镇至少连接一条公路。大保驾驶巡逻车可以从任一个村镇开始巡逻，在任意一个村镇结束。
大保想请你找出一条最佳的巡逻路径，使每条公路都恰好被巡逻过一次。如果存在多组可行的解，可以把输出的路径看成是一个 800 进制的数，输出 800 进制表示法中最小的一个 （也就是输出第一位较小的，如果第一位相同，看第二位较小的，以此类推）。输入数据保证至少有一个解。
Input
输入第一行一个整数 n，表示山区公路的数目。
Output
输出共(n+1)行，每行一个整数，依次表示路径经过的村镇编号。注意数据可能有多组解，但只要题目要求的最小的那一组解。输入数据保证至少有一个解。
Sample Input Copy
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
Sample Output Copy
1
2
3
4
2
5
4
6
5
7
HINT
。