[USACO3.3]骑马修栅栏 Riding the Fences

题目背景

Farmer John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

题目描述

John 是一个与其他农民一样懒的人。他讨厌骑马,因此从来不两次经过一个栅栏。 John 的农场上一共有 $m$ 个栅栏,每一个栅栏连接两个顶点,顶点用 $1$ 到 $500$ 标号(虽然有的农场并没有那么多个顶点)。一个顶点上至少连接 $1$ 个栅栏,没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。John 能从任何一个顶点(即两个栅栏的交点)开始骑马,在任意一个顶点结束。 你需要求出输出骑马的路径(用路上依次经过的顶点号码表示),使每个栅栏都恰好被经过一次。如果存在多组可行的解,按照如下方式进行输出:如果把输出的路径看成是一个 $500$ 进制的数,那么当存在多组解的情况下,输出 $500$ 进制表示法中最小的一个 (也就是输出第一位较小的,如果还有多组解,输出第二位较小的,以此类推)。 输入数据保证至少有一个解。

输入输出格式

输入格式


第一行一个整数 $m$,表示栅栏的数目。 从第二行到第 $(m+1)$ 行,每行两个整数 $u,v$,表示有一条栅栏连接 $u,v$ 两个点。

输出格式


共 $(m+1)$ 行,每行一个整数,依次表示路径经过的顶点号。注意数据可能有多组解,但是只有上面题目要求的那一组解是认为正确的。 数据保证至少有一组可行解。

输入输出样例

输入样例 #1

9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

输出样例 #1

1
2
3
4
2
5
4
6
5
7

说明

对于 $100\%$ 的数据,$1 \leq m \leq 1024,1 \leq u,v \leq 500$。 题目翻译来自NOCOW。 USACO Training Section 3.3