题目描述

给你一棵大小为 $n$ 的树。树上节点编号从 $1$ 到 $n$。

请你以节点 $1$ 为起点对这棵树进行深度优先遍历，并输出一个合法的深度优先遍历序列（即 DFS 序）。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树上一条边连接的两个端点的编号（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）。

数据保证这是一棵树。

输出格式

输出共一行，包含 $n$ 个整数，以空格分隔。表示一个合法的 DFS 序列。

说明：本题是 special judge，所以你只需要输出任意一个满足条件的 DFS 序即可。

样例

5
1 2
1 3
2 4
2 5

1 2 4 5 3

6
1 2
1 3
1 4
2 5
3 6

1 2 5 3 6 4

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$
• 对于 $40\%$ 的数据，$n \le 10^3$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$