当前没有测试数据。

D - 高橋之旅

分数：400分

问题描述

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

高橋将从城市$1$出发，并按照以下步骤进行旅行。

• 如果还有未访问的与当前所在城市直接相连的城市，他就去编号最小的那座城市。
• 否则，
  • 如果他在城市$1$，他结束旅行；
  • 否则，他返回到在访问当前城市之前所在的城市。

请找出高橋访问城市的顺序。

限制

• $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}$

输出

输出高橋访问城市的顺序，包括旅行开始和结束时的城市$1$，并且城市之间用空格分隔。

4
1 2
4 2
3 1

1 2 4 2 1 3 1

他的旅行过程如下：

• 开始于城市$1$。
• 与城市$1$直接相连的未访问城市有城市$2$和$3$，他去编号较小的城市，即城市$2$。
• 与城市$2$直接相连的未访问城市是城市$4$，他去了那里。
• 与城市$4$直接相连的未访问城市没有。他返回城市$2$。
• 与城市$2$直接相连的未访问城市没有。他返回到在访问城市$2$之前所在的城市$1$。
• 与城市$1$直接相连的未访问城市是城市$3$，他去了那里。
• 与城市$3$直接相连的未访问城市没有。他返回城市$1$。
• 与城市$1$直接相连的未访问城市没有。他结束了旅行。

5
1 2
1 3
1 4
1 5

1 2 1 3 1 4 1 5 1