题目描述

加粗：给定一棵包含n个节点的无向树，节点编号从1到n。请你从1号节点开始进行深度优先搜索（DFS），并按照访问要求输出遍历序列

输入描述

加粗：第一行输入一个整数n，表示树的节点总数。接下来n-1行，每行输入两个整数x和y，表示树中存在一条连接x和y的边。

输出描述

加粗：输出一行，包含2n个整数，为按照上述规则得到的DFS遍历序列，相邻两个数之间用空格隔开。

输入样例

3
1 2
1 3

输出样例

1 3 3 2 2 1 

数据范围

加粗：1≤n≤100000，保证输入的是一棵合法的树。