4918 - 树的深搜

题目描述

一棵有 N 个结点的树，树上结点编号为 1 到 N。

指定 1 号点为树的根，并给出树上所有的父子关系。

请从根开始，按照深度优先、优先访问小编号结点的顺序深搜树，并输出深搜过程中结点的访问顺序。

输入

第 1 行输入一个整数 N 代表树上结点的数量。(1 \le N \le 100)。

接下来 N-1 行，每行输入两个整数 X, Y，代表编号为 X 的结点是编号为 Y 的结点的父。

输出

输出 N 行，每行一个整数，代表按题意输出的树深搜过程中每个结点的编号。

样例

输入

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

输出

1
4
8
7
5
2
6
3

输入

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

输出

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

输入

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

输出

1
2
4
3
8
7
10
9
5
11
6
标签

树

题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 5
通过人数 2
金币数量 1 枚
难度 入门
上一题 下一题