题目描述

给定一棵树，对其进行深度优先遍历。遍历遵循以下规则：

1. 遍历时先输出根结点编号
2. 对子树遍历时输入顺序进行遍历

输入输出格式

输入格式

第一行一个整数n，表示有n个结点。 $1 \leq n \leq 1000$

接下来n-1行，每行两个整数x, y 表示x为y的父结点。

输出格式

n个整数，表示树的深度优先序列

样例

6
1 2
1 3
1 4
2 5
2 6

1 2 5 6 3 4

提示

$1 \leq n \leq 1000$