题目描述

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

• 如果当前所在城市有未访问过的直接相连城市，他会前往编号最小的那个城市。
• 否则，
  • 如果他在城市 $1$ ，旅行结束；
  • 否则，他会返回到他第一次访问当前城市之前所在的城市。

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

输入格式

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

$N$

$A_1$ $B_1$

$\vdots$

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 2
4 2
3 1

输出 #1

1 2 4 2 1 3 1

输入输出样例 #2

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

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$
• 保证可以通过道路在任意两个城市之间旅行。