Takahashi Tour

题目描述

阿托德科尔共和国有 $N$ 个城市，编号为 $1$ 到 $N$，以及编号为 $1$ 到 $N-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

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$ 直接相连且未被访问的城市有城市 $2$ 和 $3$。去编号较小的城市，也就是城市 $2$。 与城市 $2$ 直接相连且未被访问的城市是城市 $4$。去那里。 与城市 $4$ 直接相连且未被访问的城市不存在。回到城市 $2$。 与城市 $2$ 直接相连且未被访问的城市不存在。回到第一次访问城市 $2$ 之前所在的城市，也就是城市 $1$。 与城市 $1$ 直接相连且未被访问的城市是城市 $3$。去那里。 与城市 $3$ 直接相连且未被访问的城市不存在。回到城市 $1$。 与城市 $1$ 直接相连且未被访问的城市不存在。结束旅行。

标签: AtCoder|abc213D

来源

AtCoder|abc213D