题目描述

给定一棵以1号结点为根的有根树，求先序遍历、后序遍历、层次遍历和叶结点遍历。每个结点的孩子按输入顺序访问。

输入格式

第一行n。接下来n-1行，每行u、v，表示u是v的父结点。

输出格式

依次输出四行：先序、后序、层次、叶结点遍历，每行结点编号以空格分隔。

样例

9
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9

1 2 4 8 9 5 3 6 7
8 9 4 5 2 6 7 3 1
1 2 3 4 5 6 7 8 9
8 9 5 6 7

数据范围

1≤n≤1000；输入构成以1为根的树。