← 返回题目列表

AtCoder · abc213_d

G. 高桥之旅

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

AtCoder 共和国有 N 城市编号 1 通过 N 和 N-1 道路编号 1 通过 N-1。 道路 i 连接城市 A_i 和城市 B_i 双向。保证人们可以通过道路在每一对城市之间出行。

高桥将离开城市 1 并通过重复以下操作来开始旅程。

  • 如果有未访问的城市与高桥现在所在的城市直接相连,他会前往这些城市中数量最少的城市。
  • 否则,
    • 如果他在城市 1,他结束旅程;
    • 否则,他会前往他第一次访问当前城市之前所在的城市。

按照高桥访问城市的顺序查找他访问过的城市的序列。

约束

  • 2 \leq N \leq 2\times 10^5
  • 1\leq A_i,B_i \leq N
  • 可以使用道路在每对城市之间行驶。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

输出

按照高桥访问的顺序打印他访问过的城市的序列,包括 City 1 位于旅程的开始和结束处,中间有空格。


示例输入 1

4
1 2
4 2
3 1

示例输出 1

1 2 4 2 1 3 1

他的旅程如下。

  • 从城市开始 1.
  • 与城市直连的未访问城市 1 是城市 2 和 3。去数字较小的城市,即City 2.
  • 与 City 直接相连的未访问城市 2 是城市 4。去那里吧。
  • 没有与 City 直接相连的未访问过的城市 4。返回城市 2.
  • 没有与 City 直接相连的未访问过的城市 2。前往城市 1,他在访问曼城之前所在的地方 2 第一次。
  • 与 City 直接相连的未访问城市 1 是城市 3。去那里吧。
  • 没有与 City 直接相连的未访问过的城市 3。返回城市 1.
  • 没有与 City 直接相连的未访问过的城市 1。结束旅程。

示例输入 2

5
1 2
1 3
1 4
1 5

示例输出 2

1 2 1 3 1 4 1 5 1