题目描述

给定一棵二叉树，依次输出先序、中序、后序遍历的序列。 每种序列一行。

输入格式

第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n（1<= n <= 10） ， 根结点为 1。接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有两个整数， 分别表示该结点的左儿子和右儿子的结点编号。 如果第一个（第二个） 数为-1 则表示没有左（右） 儿子。

输出格式

3行，依次输出先序、中序、后序遍历的序列。每种序列一行。行内结点编号之间空格隔开。

样例

输入样例 1

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

输出样例 1

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

输入样例 2

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

输出样例 2

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

输入样例 3

4
2 -1
3 -1
4 -1
-1 -1

输出样例 3

1 2 3 4 
4 3 2 1 
4 3 2 1

输入样例 4

4
-1 2
-1 3
-1 4
-1 -1

输出样例 4

1 2 3 4 
1 2 3 4 
4 3 2 1