题目描述

现有一棵包含 $n$ 个结点的二叉树（$n \le 10^6$），结点按 $1$ 到 $n$ 编号，根结点固定为 $1$ 号。我们会告诉你每个结点的左、右孩子分别是几号（编号同样不超过 $n$）；当某个方向上没有孩子时，对应位置给出 $0$，因此叶子结点会给出 0 0。

请你根据这些信息把这棵二叉树还原出来，然后依次求出它的前序遍历、中序遍历与后序遍历。

输入格式

第一行一个整数 $n$，表示结点总数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l$、$r$，依次代表结点 $i$ 的左孩子与右孩子编号；$l=0$ 表示左孩子不存在，$r=0$ 同理。

输出格式

共输出三行，每行 $n$ 个整数，用空格分隔。

第一行为该二叉树的前序遍历结果，第二行为中序遍历结果，第三行为后序遍历结果。

样例

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

提示

对于 $1\leq n\leq 10^5$ 的测试数据，时间限制为 1 秒；对于 $10^5\lt n\leq 10^6$ 的测试数据，时间限制为 3 秒。