33 - 树的遍历

已知N个节点的一个树,节点编号从1N

求其DFS序,请输出字典序最小的DFS序。

DFS序:一棵树从根节点出发,DFS遍历时依次经过的节点序列。

输入

输入第一行包含两个整数N,分别表示点的个数。(N <= 1000

接下来输入N-1行,每行两个整数u, v表示有一条u,v相连的边

输出

输出N个点的最小字典序遍历结果

样例

输入

4
1 2
1 3
3 4

输出

1 2 3 4

输入

5
1 3
1 4
3 2
2 5

输出

1 3 2 5 4
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题