题目描述

给定一棵以 1 号结点为根的无向树，请按照深度优先搜索（DFS）的顺序遍历整棵树。

为了使答案唯一，访问某个结点的相邻结点时，必须按照结点编号从小到大的顺序递归访问。

输入格式

第一行包含一个整数 n，表示树的结点数。

接下来 n-1 行，每行包含两个整数 u 和 v，表示 u 与 v 之间有一条无向边。

输出格式

输出一行，包含 n 个整数，表示从 1 号结点开始的 DFS 遍历序。

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

1 2 4 5 3 6 7

样例分析

从 1 号结点开始遍历。由于题目规定相邻结点按编号从小到大访问，所以遍历序唯一。

数据范围与提示

对于 100% 的数据，1 ≤ n ≤ 100000，1 ≤ u,v ≤ n。输入保证给出的是一棵树。