给定一棵大小为n，根为1的树，求出其dfs序、bfs序。

请将所有出点按照编号从小到大排序后进行遍历。

解释：dfs为深度优先搜索，bfs为宽度优先搜索。

输入格式

一个整数n，表示点的个数。(1 \le n \le 50)

接下来一行n-1个整数，分别表示点2\sim n节点的父亲。(1 \le fa_i \le n)

输出格式

第一行输出dfs序，第二行输出bfs序。

样例输入1

4
1 1 2

样例输出1

1 2 4 3
1 2 3 4

样例输入2

5
1 2 2 4

样例输出1

1 2 3 4 5
1 2 3 4 5