D. 二叉树遍历

题目描述

给出每个节点的两个儿子节点，建立一棵二叉树（根节点为 $1$），如果是叶子节点，则输入 $0$ $0$。建好树后希望知道这棵二叉树的先序遍历、中序遍历和后序遍历。 最多有 $10^5$ 个结点。

输入格式

第一行一个正整数 $n$，表示有 $n$ 个节点。 接下来 $n$ 行，每行两个正整数，表示第 $i$ 个节点的儿子节点。

输出格式

输出有三行，分别是先序遍历、中序遍历、后序遍历。

样例

输入

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

输出

1 2 3 4 5 6 7
4 3 5 2 6 1 7
4 5 3 6 2 7 1

数据范围与提示

• $1 \le n \le 10^5$