题目描述

AtCoder 共有 $N$ 个编号为 $1$ 到 $N$ 的城市和 $N-1$ 条编号为 $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$。
• 没有与城市 $4$ 直接相连的未被访问过的城市。返回城市 $2$。
• 没有与城市 $2$ 直接相连的未被访问过的城市。前往上次访问城市 $2$ 之前的城市，即城市 $1$。
• 与城市 $1$ 直接相连的未被访问过的城市是城市 $3$。前往城市 $3$。
• 没有与城市 $3$ 直接相连的未被访问过的城市。返回城市 $1$。
• 没有与城市 $1$ 直接相连的未被访问过的城市。结束旅行。

示例输入 2

5
1 2
1 3
1 4
1 5

示例输出 2

1 2 1 3 1 4 1 5 1