← 返回题目列表

AtCoder · indeednow_2015_qualc_3

C. 树

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

問題文

树是由顶点和连接它们的边组成的结构“图”的一种, 1 顶点的数量为 N 个时,边的数量为 N-1 条,每个顶点都通过边直接或间接地与其他所有顶点相连。

在这个问题中,顶点有 N 个,1 假设一直下雨,直到 N 被编号到

当给定一棵树时,请输出通过以下操作生成的数列中字典序最小的一个。

  1. 当给定一棵树时,请输出通过以下操作生成的数列中,字典序最小的一个。
  2. 选择顶点1。
  3. 从至今已选择的顶点所连接的边中,选择还未被选择的顶点,每次选择一个,重复此操作直到没有尚未选择的顶点。

按照被选择的顺序列出顶点编号,形成数列。 N 长度为 A=\{a_1,a_2, ...,a_N\} 和 在 B=\{b_1,b_2, ...,b_N\} 的序列,按字典序 A 是 时间保证在 B 小于,意味着

  • i < k 在 a_i=b_i
  • i = k 在 a_i<b_i

中 k(1≦k≦N) 存在。


入力

输入是按以下格式从标准输入给出的。

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
  • 1 行表示树的顶点数的整数。 N (2 ≦ N ≦ 10^5) 。 来自行
  • 2 从行 N-1 行给出了树的边的信息。在这些中, i (1 ≦ i ≦ N-1) 行表示顶点 a_i 和边 b_i 相连的边 2 整数 a_i , b_i 。 来自行
  • N-1 本的边连接 N 个顶点构成树。

部分点

针对该问题设置了部分分数。 满足

  • 50 在点的测试用例中, 1 ≦ N ≦ 3,000 满足。

出力

1 上,输出从给定树创建的按字典顺序排列的最小数字序列,并用空格分隔。

不要忘记行尾的换行符。另外,不要在行尾包含额外的空格。


入力例1

4
1 3
1 4
2 3

出力例1

1 3 2 4

这是问题文本图中的树。

一、顶点 选择 1 。

接下来,顶点 选择 3 。顶点 2 是迄今为止选择的顶点(在本例中,顶点 请注意, 1 没有通过边连接,因此无法选择。

接下来,顶点 选择 2 。

接下来,顶点 选择 4 。

如果按照选择的顺序排列顶点编号,1 3 2 4 。按字典顺序,没有比此列更小的选择。


入力例2

6
1 2
2 3
2 6
6 4
1 5

出力例2

1 2 3 5 6 4

入力例3

7
1 5
5 2
5 3
5 7
5 6
6 4

出力例3

1 5 2 3 6 4 7