题目描述

小高将在AtCoder共和国进行一次旅行。该国有$N$个城市，编号从$1$到$N$，以及$N-1$条道路，编号从$1$到$N-1$。第$i$条道路双向连接城市$A_i$和$B_i$。保证可以通过这些道路在任意两个城市之间旅行。 小高将从城市$1$出发，并按以下规则重复进行旅行：

• 如果当前所在城市有未访问过的直接相连城市，他会前往编号最小的那个城市。

• 否则，

  • 如果他在城市$1$，旅行结束；
  • 否则，他会返回到他第一次访问当前城市之前所在的城市。

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

输入格式

输入从标准输入中以下列格式给出：

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\cdots$

$A_{N-1}$ $B_{N-1}$

输出格式

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

样例

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

样例1解释

他的旅程如下：

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

数据范围

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

来源

• AtCoder ABC213D