题目描述

The Republic of AtCoder has $N$ cities numbered $1$ through $N$ and $N - 1$ roads numbered $1$ through $N - 1$ Road $i$ connects City $A_i$ and City $B_i$ bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.

Takahashi will depart City $1$ and have a journey by repeating the following.

• If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.
• Otherwise,
• if he is in City $1$, he ends the journey;
• otherwise, he goes to the city he was in just before visiting the current city for the first time.

输入格式

Input is given from Standard Input in the following format:

$N$

$A_1 B_1$

⋮

$A_N−1 B_N−1$

输出格式

Print the sequence of cities visited by Takahashi in the order he visits them, including City $1$ at the beginning and end of the journey, with spaces in between.

样例

4 
1 2 
4 2 
3 1 

1 2 4 2 1 3 1 

5 
1 2 
1 3 
1 4 
1 5 

1 2 1 3 1 4 1 5 1 

提示

$2\\le N \\le 2\\cdot 10^5$

$1\\le A_i,B_i \\le N$

It is possible to travel between every pair of cities using roads.

来源：https://atcoder.jp/contests/abc213/tasks/abc213_d

转录 By QLU_钟志强