102133: [AtCoder]ABC213 D - Takahashi Tour

Problem Statement

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.

Find the sequence of cities visited by Takahashi in the order he visits them.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $1\leq A_i,B_i \leq N$
• It is possible to travel between every pair of cities using roads.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

Output

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.

Sample Input 1

4
1 2
4 2
3 1

Sample Output 1

1 2 4 2 1 3 1

His journey will be as follows.

• Start in City $1$.
• The unvisited cities directly connected to City $1$ are City $2$ and $3$. Go to the city with the smaller number, that is, City $2$.
• The unvisited city directly connected to City $2$ is City $4$. Go there.
• There is no unvisited city directly connected to City $4$. Go back to City $2$.
• There is no unvisited city directly connected to City $2$. Go to City $1$, where he was in just before visiting City $2$ for the first time.
• The unvisited city directly connected to City $1$ is City $3$. Go there.
• There is no unvisited city directly connected to City $3$. Go back to City $1$.
• There is no unvisited city directly connected to City $1$. End the journey.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

1 2 1 3 1 4 1 5 1

问题描述

在AtCoder共和国，有编号为1到N的N个城市和编号为1到N-1的N-1条道路。道路i双向连接城市$A_i$和城市$B_i$。保证可以通过道路在任何两个城市之间旅行。

Takahashi将从城市1出发，重复以下操作：

• 如果有未访问过的、与当前城市直接相连的城市，他将前往这些城市中编号最小的城市。
• 否则，
  • 如果他在城市1，结束旅程；
  • 否则，他将前往他第一次访问当前城市前所在的城市。

找出Takahashi访问过的城市，按照他访问的顺序列出。

约束

• $2 \leq N \leq 2\times 10^5$
• $1\leq A_i,B_i \leq N$
• 可以通过道路在任何两个城市之间旅行。

输入

输入格式如下：

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出

打印Takahashi访问过的城市，包括旅程开始和结束时的城市1，用空格隔开。

样例输入1

4
1 2
4 2
3 1

样例输出1

1 2 4 2 1 3 1

他的旅程如下：

• 在城市1开始。
• 与城市1直接相连的未访问过的城市是城市2和3。前往编号较小的城市，即城市2。
• 与城市2直接相连的未访问过的城市是城市4。前往那里。
• 与城市4没有直接相连的未访问过的城市。返回城市2。
• 与城市2没有直接相连的未访问过的城市。前往城市1，即他第一次访问城市2前所在的城市。
• 与城市1直接相连的未访问过的城市是城市3。前往那里。
• 与城市3没有直接相连的未访问过的城市。返回城市1。
• 与城市1没有直接相连的未访问过的城市。结束旅程。

样例输入2

5
1 2
1 3
1 4
1 5

样例输出2

1 2 1 3 1 4 1 5 1