4233: Takahashi Tour

# Takahashi Tour ### 内存 1024MB ### 时间 2S ## 题目描述 小高将在AtCoder共和国进行一次旅行。该国有$N$个城市，编号从$1$到$N$，以及$N-1$条道路，编号从$1$到$N-1$。第$i$条道路双向连接城市$A_i$和$B_i$。保证可以通过这些道路在任意两个城市之间旅行。 小高将从城市$1$出发，并按以下规则重复进行旅行： - 如果当前所在城市有未访问过的直接相连城市，他会前往编号最小的那个城市。 - 否则， - 如果他在城市$1$，旅行结束； - 否则，他会返回到他第一次访问当前城市之前所在的城市。 请找出小高访问城市的顺序序列。 ## 输入格式 输入从标准输入中以下列格式给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_{N-1}$ $B_{N-1}$ ## 输出格式 输出小高访问城市的顺序序列，包括旅程开始和结束时的城市$1$，城市之间用空格分隔。 ## 输入输出样例 ### 输入样例1 ``` 4 1 2 4 2 3 1 ``` ### 输出样例1 ``` 1 2 4 2 1 3 1 ``` ### 输入样例2 ``` 5 1 2 1 3 1 4 1 5 ``` ### 输出样例2 ``` 1 2 1 3 1 4 1 5 1 ``` ## 数据范围与提示 【样例1说明】 他的旅程如下： - 从城市1开始。 - 城市1直接相连的未访问城市有城市2和3。前往编号较小的城市2。 - 城市2直接相连的未访问城市是城市4。前往那里。 - 城市4没有直接相连的未访问城市。返回城市2。 - 城市2没有直接相连的未访问城市。返回到第一次访问城市2之前所在的城市1。 - 城市1直接相连的未访问城市是城市3。前往那里。 - 城市3没有直接相连的未访问城市。返回城市1。 - 城市1没有直接相连的未访问城市。旅程结束。 【数据范围】 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq A_i, B_i \leq N$ - 保证可以通过道路在任意两个城市之间旅行。 ## 题目来源 ABC213D