给定一棵有根二叉树，节点编号为 $1$ 到 $n$。请分别输出它的先序遍历、中序遍历和后序遍历。

先序遍历的顺序是根、左子树、右子树；中序遍历的顺序是左子树、根、右子树；后序遍历的顺序是左子树、右子树、根。每一种遍历都从整棵树的根节点开始。

输入格式

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

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，分别表示节点 $i$ 的左孩子和右孩子。编号 $0$ 表示相应孩子不存在。输入保证这些数据恰好构成一棵有根二叉树。

输出格式

依次输出标题 Preorder、Inorder、Postorder，每个标题下一行输出对应的节点编号序列，每个节点编号前保留一个空格。

1
0 0

Preorder
 1
Inorder
 1
Postorder
 1

2
0 2
0 0

Preorder
 1 2
Inorder
 1 2
Postorder
 2 1

3
0 2
3 0
0 0

Preorder
 1 2 3
Inorder
 1 3 2
Postorder
 3 2 1

数据范围与约定

• $1\le n\le25$
• 输入恰好描述一棵合法二叉树。