题目描述

给定一棵拥有 n 个节点的树(结点编号 1∼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

Copy

输出#1

1 2 7 3 5 6 4 8 9

Copy

数据范围

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