题目描述

给你一棵 $n$ 个节点的二叉树，节点的编号为 1 到 $n$，二叉树的根为 1 号节点。请你求出这棵二叉树的先序、中序和后序遍历的结果。

输入格式

第一行一个整数 $n$ 表示节点数。

接下来 $n$ 行，每行两个整数，第一个整数表示 $i$ 号节点的左儿子的编号，第二个整数表示 $i$ 号节点的右儿子的编号，如果某个数字为 0 表示没有对应的子节点。

输入保证是一棵二叉树。

输出格式

输出三行，每行 $n$ 个数代表一种遍历的结果。

第一行为先序遍历的结果，第二行为中序遍历的结果，第三行为后序遍历的结果。

4
2 3
0 0
4 0
0 0

1 2 3 4
2 1 4 3
2 4 3 1

数据规模

对于所有数据，保证 $1≤n≤1024$。