题目描述

有一棵有n个节点的二叉树，给出每个节点的子节点编号，建立一棵二叉树（根节点为A），如果是叶子节点，则输入0 0。

建好这棵二叉树之后，分别求出它的先序，中序和后序遍历。

输入格式

第 1 行一个正整数n表示该二叉树节点总数； 接下的 n 行，第 i 行两个字符 l，r 分别表示结点i的左右子节点，若 l 为‘0'，则表示无左子节点，同理若 r 为 '0'，则表示无右子节点。

输出格式

第 1 行，为n个数（中间一个空格间隔），表示这棵二叉树的先序遍历； 第 2 行，为n个数（中间一个空格间隔），表示这棵二叉树的中序遍历； 第 3 行，为n个数（中间一个空格间隔），表示这棵二叉树的后序遍历；

样例1

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

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

样例2

4 3 10

1

数据范围

1 ≤ n, ≤ 500; 数据保证节点编号均为1~n之间的正整数。