Background

求一棵二叉树的前序遍历，中序遍历和后序遍历

Format

Input

第一行一个整数n，表示这棵树的节点个数。

接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。

Output

输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。

Samples

输入数据 input1
5
2 3
4 5
0 0
0 0
0 0
```输出数据 output1
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

Limitation

$n \le 16$，默认结点 $1$ 为树根。