孩子兄弟的前后根序

难度：T2

【知识点：树表示与遍历】

前置知识：二叉树、编号数组、孩子兄弟和递归遍历。

题目描述

给出一棵有序根树的孩子兄弟表示：first[u]是第一个孩子，nxt[u]是同父下一个兄弟，0表示没有。根没有兄弟。输出原树前根序（先根再依序各孩子子树）及后根序（依序完成所有孩子子树再根）。不是把first当左、nxt当右后二叉树的后序。

输入格式

第一行n r；随后n行，第i行first[i] nxt[i]。保证全部结点恰好构成题意所述合法树。

输出格式

两行，第一行原树前根序，第二行原树后根序。

样例输入

4 1
2 0
4 3
0 0
0 0

样例输出

1 2 4 3
4 2 3 1

样例解释

原树根1依序有孩子2、3；2有孩子4，故前根1 2 4 3，后根4 2 3 1。

数据范围

1≤n≤20。普通结点编号在1..n，空孩子/兄弟记0。