题目描述

给定一棵拥有 $n$ 个节点的树(结点编号 $1\sim n$)，结点 1 为根节点，遍历树，按照深度优先遍历的先后顺序输出节点编号。

输入格式

第 1 行一个整数 $n$，表示树中节点的数量。接下来若干行，每行两个整数 $x, y$，表示 $x$ 是 $y$ 的父节点。

输出格式

输出一行，按照深度优先遍历的先后顺序输出节点编号，在遍历一个节点的所有子树时， 优先遍历根节点编号较小的子树。输出的编号之间用空格分隔。

样例

输入#1

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

输出#1

1 2 7 3 5 6 4 8 9

数据范围

对于 100% 的测试数据满足：$1≤n≤100$。