You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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$ 为树根。