#1013. 树的遍历

树的遍历

问题描述

给出一棵含有 N 个结点的树,结点编号为 1 ~ N,其中1 号为根结点。从根结点开始遍历,输出它的 DFS 和 BFS 序列。如果有多种可能的序列,输出字典序最小的。

输入

第一行:N

接下来 N-1 行,每行两个数 u, v, 表示 u 和 v 之间有一条边。

输出

两行,依次为 DFS 和 BFS 遍历的序列,具体格式见样例。注意:输出中的每个整数前面均有一个空格。

样例输入

12
1 4
1 2
3 1
2 5
6 2
11 5
5 10
4 7
4 9
8 4
12 7

样例输出

DFS: 1 2 5 10 11 6 3 4 7 12 8 9
BFS: 1 2 3 4 5 6 7 8 9 10 11 12

数据范围

1 ≤ N ≤ 50,000