提示: 欢迎访问OurACM平台。
Problem 2227 邮票

Accept: 64    Submit: 198
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一天Bob收到一封信。Bob知道瓦罗兰大陆的邮局从A城市送信到B城市,乐意使用从A城市到B城市的邮票(A, B),或者使用从B城市到A城市的邮票(A, B),但是由于瓦罗兰大陆的城市繁多,所以并不是所有城市之间都能直接发送接收信件,换句话说,某两个城市想要通行邮件必须经过其他城市才行,但是邮局发送一次邮件的路途中从不会通过一座城市两次。

现在在Bob的信封上有N个邮票,Bob想知道这封信件是如何周转到达他手中的。

Input

题目有多组数据。

每组数据第一行包含一个整数,N ( 2 <= N <= 1e5),代表信件上的N封邮票。

接下有N行数据。第 i 行数据包含两个整数 ui,vi,代表从城市ui发送到城市vi的邮票,ui代表城市的编号,每个城市的编号互不相同,(ui != vi ,1 <= ui, vi <= 1e9)。

输入数据保证有解。

Output

每组样例的结果输出为一行, 每行包括N+1个被空格隔开的整数,代表着信件依次经过的城市编号。

若有多组可行答案,输出字典序最小的那组答案。

Sample Input

2 1 100 100 2 3 3 1 100 2 3 2

Sample Output

1 100 2 1 3 2 100

Source

FOJ有奖月赛-2016年4月(校赛热身赛)

Submit  Back  Status  Discuss