题目描述

给定一棵以 $1$ 号结点为根的二叉树，结点编号为 $1 \sim n$。对于每个结点，输入给出它的左儿子和右儿子编号；如果某个儿子不存在，用 $0$ 表示。输入保证这些结点构成一棵合法的二叉树。

请你输出这棵二叉树的先序遍历序列。先序遍历规则：先访问根结点，再先序遍历左子树，最后先序遍历右子树。

输入格式

第一行一个整数 $n$，表示结点个数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i, r_i$，分别表示结点 $i$ 的左儿子和右儿子编号。若不存在，则对应位置为 $0$。

输出格式

输出一行，共 $n$ 个整数，表示先序遍历序列，相邻两个整数之间用一个空格隔开。

样例

5
2 3
4 5
0 0
0 0
0 0

1 2 4 5 3

样例分析
结点 $1$ 的左儿子是 $2$，右儿子是 $3$；结点 $2$ 的左儿子是 $4$，右儿子是 $5$。按照先序遍历规则递归访问，得到序列 $1, 2, 4, 5, 3$。

数据范围

对于 $100\%$ 的数据：$1 \le n \le 1000$。