高桥旅行记

题目描述

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$,城市之间以空格分隔。

样例

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

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• 保证利用道路可以在任意两座城市之间往返