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

在这个问题中,顶点有 N 个,1 假设一直下雨,直到 N 被编号到
当给定一棵树时,请输出通过以下操作生成的数列中字典序最小的一个。
- 当给定一棵树时,请输出通过以下操作生成的数列中,字典序最小的一个。
- 选择顶点1。
- 从至今已选择的顶点所连接的边中,选择还未被选择的顶点,每次选择一个,重复此操作直到没有尚未选择的顶点。
按照被选择的顺序列出顶点编号,形成数列。 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