[ABC213D] Takahashi Tour

题目描述

给定一个 $n$ 个结点的树，其根结点为 $1$。

求出它的欧拉序。特别地，如果有多个可以遍历的结点，先遍历编号较小的。

有𝑁个城市，编号从1到𝑁，以及𝑁−1条道路，编号从1到𝑁−1。 道路𝑖双向连接城市𝐴𝑖和城市𝐵𝑖。保证可以通过道路到达每一对城市。

小明将从城市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

提示

【样例一说明】

他的行程如下：

从城市1出发。

直接连接到城市1的未访问城市是城市2和3。前往编号较小的城市，即城市2。

直接连接到城市2的未访问城市是城市4。前往该城市。

直接连接到城市4的未访问城市不存在。返回城市2。

直接连接到城市2的未访问城市不存在。前往城市1，即他第一次访问城市2之前所在的城市。

直接连接到城市1的未访问城市是城市3。前往该城市。

直接连接到城市3的未访问城市不存在。返回城市1。

直接连接到城市1的未访问城市不存在。结束行程。

【数据范围】

$2≤𝑁≤2×10^5$

$1≤A_i​,B_i​≤N$

可以通过道路到达每一对城市。