AT_abc213_d [ABC213D] Takahashi Tour

在 AtCoder 国，有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $N-1$ 条道路，编号为 $1$ 到 $N-1$。 通过第 $i$ 条道路，可以在城市 $A_i$ 和城市 $B_i$ 之间双向移动。保证所有城市之间都可以通过道路互相到达。 高桥君从城市 $1$ 出发，按照以下规则进行旅行： - 如果当前所在城市与之直接相连的城市中，存在尚未访问过的城市，则前往这些城市中编号最小的城市。 - 如果不存在这样的城市： - 如果当前城市是城市 $1$，则结束旅行。 - 否则，返回到第一次到达当前城市时所处的前一个城市。 请按顺序输出高桥君在旅行过程中访问的城市，包括旅行开始和结束时的城市 $1$。

输入以如下格式从标准输入读入： > $N$ > $A_1$ $B_1$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$

请按顺序输出高桥君访问的城市编号（包括旅行开始和结束时的城市 $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$。 - 与城市 $4$ 直接相连且未访问的城市没有，返回到上一次在城市 $4$ 前所处的城市 $2$。 - 与城市 $2$ 直接相连且未访问的城市没有，返回到上一次在城市 $2$ 前所处的城市 $1$。 - 与城市 $1$ 直接相连且未访问的城市有 $3$，前往城市 $3$。 - 与城市 $3$ 直接相连且未访问的城市没有，返回到上一次在城市 $3$ 前所处的城市 $1$。 - 与城市 $1$ 直接相连且未访问的城市没有，旅行结束。 由 ChatGPT 4.1 翻译