题目描述

AtCoder 共和国有 $N$ 个城市，编号为 $1$ 至 $N$ ， $N-1$ 条道路，编号为 $1$ 至 $N-1$ 。道路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$ 。可以保证，人们可以通过道路来往于每一对城市之间。

高桥将从城市 $1$ 出发，通过重复以下步骤进行旅行。

• 如果有与高桥现在所在的城市直接相连的未到城市，他将前往这些城市中编号最小的城市。
• 否则
  • 如果他在城市 $1$ ，则结束旅程；
  • 否则，他会前往首次访问当前城市前所在的城市。

按照高桥访问城市的顺序找出他访问的城市序列。

输入格式

第一行输入 $N$

接下来 $N-1$ 行，每行输入两个整数代表 $A_i$ $B_i$

输出格式

输出若干个数字，用空格隔开。代表旅行访问城市的编号顺序。若有多个城市离自己最近，会优先访问编号最小的城市。

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\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\leq\ A_i,B_i\ \leq\ N$
• 给定的图连通

样例 1 解释

他的行程如下

• 从城市 $1$ 开始。
• 与城市 $1$ 直接相连的未游览城市是城市 $2$ 和 $3$ 。前往数字较小的城市，即城市 $2$ 。
• 与城市 $2$ 直接相连的未访问城市是城市 $4$ 。去那里。
• 没有与城市 $4$ 直接相连的未到访城市。返回城市 $2$ 。
• 没有与城市 $2$ 直接相连的未游览城市。前往城市 $1$ ，即他第一次访问城市 $2$ 之前所在的城市。
• 与城市 $1$ 直接相连的未到访城市是城市 $3$ 。前往那里。
• 没有与城市 $3$ 直接相连的未到访城市。返回城市 $1$ 。
• 没有与城市 $1$ 直接相连的未游览城市。结束旅程。