思路与算法

给定一棵无根树（节点编号 1 到 n），可以从任意节点出发做 DFS，且每个节点遍历相邻节点的顺序可以任意安排。希望得到整段访问序列在字典序上最小的结果。

关键观察

字典序最小的 DFS 序列意义是：尽早访问小编号的节点。

• 起点可以任意选，显然选编号最小的节点作为起点最有利（因为序列第一个元素越小越好）。编号范围是 1..n，起点选 1 即可。
• 在 DFS 过程中，每个节点应先访问编号小的未访问邻居，才能保证当前局部扩展在字典序上最小。

题目内容

给定一棵无根树，包含 $n$ 个节点，节点编号为 $1$ ~ $n$ 。小 $C$ 可以从任意节点出发，对这棵树进行深度优先搜索($DFS$)遍历，记录访问节点的编号序列作为 $DFS$ 序。

在遍历过程中，每个节点可以按照任意顺序访问其相邻节点。小$C$希望得到字典序最小的 $DFS$ 序。请你计算并输出该序列。

【名词解释】

• $DFS$ 遍历：DFS遍历 指从指定起始节点出发，每次访问一个未被访问的相邻节点，并继续递归，直到所有可达节点均被访问。

• $DFS$ 序：DFS序 为 $DFS$ 遍历过程中访问节点的编号序列。

• 字典序：字典序 从两个序列的第一个元素开始逐个比较，直至遇到第一个不同元素，通过比较该位置元素大小决定序列大小。

输入描述

第一行输入一个整数 $n(1≦n≦10^6)$，表示树的节点数量。

接下来 $n-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$ $(1≦u_i,v_i≦n;u_i≠v_i)$，表示一条无向边。

输出描述

输出一行，共 $n$ 个整数，用空格分隔，表示字典序最小的 $DFS$ 序列。

样例1

输入

5
1 2
1 3
2 4
2 5

输出

1 2 4 5 3

样例2

输入

6
1 3
1 2
2 5
2 4
5 6

输出

1 2 4 5 6 3