题目描述

给出一棵包含 $n$ 个节点的二叉树。每个节点都有一个唯一的整数编号。 请你按照以下三种顺序输出该二叉树的节点编号：

1. 前序遍历（Pre-order）：根节点 -> 左子树 -> 右子树
2. 中序遍历（In-order）：左子树 -> 根节点 -> 右子树
3. 后序遍历（Post-order）：左子树 -> 右子树 -> 根节点

输入格式

第一行包含一个整数 $n$，表示节点数量。 接下来 $n$ 行，每行包含三个整数 $id, l, r$，分别表示当前节点编号、左孩子编号、右孩子编号。 如果左孩子或右孩子不存在，则用 $0$ 表示。 （输入保证 $1$ 号节点为根节点）

输出格式

输出共三行：

• 第一行：前序遍历序列
• 第二行：中序遍历序列
• 第三行：后序遍历序列 （每个序列中的整数之间用空格隔开）

输入输出样例

样例输入 1

3
1 2 3
2 0 0
3 0 0

样例输出 1

1 2 3
2 1 3
2 3 1

说明/提示

样例 1 结构：

• 根节点为 1，左孩子为 2，右孩子为 3。
• 前序：1 2 3
• 中序：2 1 3
• 后序：2 3 1

数据范围：

• $1 \le n \le 1000$
• $1 \le id \le n$