题目描述

给定一棵二叉树，其中包括$n$个结点，结点编号为$1 \sim n$,保证根节点编号为$1$。同时每个结点有两个子节点，第一个结点代表左子树，第二个结点代表右子树，子节点如果为$0$则代表没有这个结点。现在请你输出这棵树的中序遍历序列。

输入格式

• 第一行输入一个整数$n$代表节点数。
• 接下来$n$行，每行两个整数，代表第$i$个结点的左右子节点。

输出格式

输出中序遍历序列，每个节点中间以空格隔开。

样例

6
2 3
4 0
5 6
0 0
0 0
0 0

4 2 1 5 3 6

提示

样例1解释

样例$1$所给的二叉树如下图:

数据范围

对于所有测试数据，保证：$1 \leq n \leq 10^5$，同时根节点一定为$1$号节点。