迈克斯·豪威尔是 Mac 上著名软件 Homebrew 的作者，他去谷歌面试的时候，被每天使用他的软件工作的工程师给拒绝了，因为他没能在白板上写出翻转二叉树的代码……

现在你的机会来了，请证明你会写翻转二叉树（将树中每个结点的左右孩子互换）的程序！

输入格式

输入第一行给出正整数 N（≤ 10），是树中结点的个数（结点从 0 到 N-1 编号）。随后 N 行，第 $i$ 行（i=0, … , N-1）给出编号为 i 的结点的左、右孩子的编号。如果该孩子结点不存在，则在相应位置上用 - 表示。孩子结点间以一个空格分隔。

输出格式

首先将输入的二叉树进行翻转，然后第一行输出结果树的层序遍历序列，第二行给出其中序遍历序列。数字间必须以 1 个空格分隔，行首尾不得有多余空格。

输入样例

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例

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

限制

时间限制：4000，内存限制：65536