John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。

John 的农场上一共有 m 个栅栏，每一个栅栏连接两个顶点，顶点用 1 到 500 标号（注意不是每个农场都有这么多顶点，但始终保证标号在1~500之间）。一个顶点上至少连接 1 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。

你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 500 进制的数，那么当存在多组解的情况下，输出 500 进制表示法中最小的一个 （也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。

输入数据保证至少有一个解。

第一行一个整数 m，表示栅栏的数目。

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

对于 100% 的数据，1≤m≤1024,1≤u,v≤500。

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

数据保证至少有一组可行解。

1.在一个图中，能从一个点出发，走完所有的边，并且每条边只能走一次，最后回到出发点，这样的路径就叫做欧拉回路，有欧拉回路的图就叫欧拉图。 在欧拉图中，所有点连接的边都为偶数条。

2.在一个图中，能从一个点出发，走完所有的边，并且每条边只能走一次，这样的路径就叫做欧拉路径（不一定回到起点），有欧拉路径的图就叫半欧拉图。 在半欧拉图中，有两个点连接的边数为奇数条边（这两个点是路径的起点和终点），其余所有点连接的边都为偶数条。