时间限制： 1.0 秒

空间限制： 64 MB

题目背景

对于任意形态的有根有序树，都可以利用“长子-兄弟表示法”将其转化为一棵二叉树。具体规则为：

• 将一个节点的所有子节点按照某种规则排好先后顺序。
• 将排序后的第一个子节点放在新树中，原节点的左子节点位置。
• 其他子节点在新树中，放在原树中前一个子节点的右子节点位置。

题目描述

在本题中你需要将一个有 $n$ 个节点的有根有序树（节点编号分别为 $1\sim n$）按照“长子-兄弟表示法”将其转化为一棵二叉树。

为了简化题意，我们保证：

• 本题中给出的有根有序树保证以 $1$ 为根；
• 对于 $i$ 号节点（$2\le i\le n$），其父亲节点的编号 $f_i$ 保证 $1\le f_i<i$；
• 每个节点的子节点按照编号从小到大规定顺序，其中编号最小的子节点为长子节点。

请注意本题的空间限制，这意味着我们不允许你使用递归的方式进行二叉树的转化，辅助空间复杂度也要满足一定的限制。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示有根有序树的节点个数。

输入的第二行包含 $n-1$ 个正整数 $f_2,\cdots,f_n$，表示 $2\sim n$ 号节点的父亲。

输出格式

输出到标准输出。

输出 $n$ 行，每行两个整数（中间用一个空格分隔），分别表示转化的二叉树当中， $i$ 号节点的左子节点和右子节点的编号。特殊地，若其左/右子节点不存在，则对应位置输出 $0$。

6
1 1 3 3 1

2 0
0 3
4 6
0 5
0 0
0 0

样例 1 解释

原始的树和转化的二叉树结构如下图：

6
1 2 3 4 5

2 0
3 0
4 0
5 0
6 0
0 0

样例 2 解释

原始的树和转化的二叉树结构如下图：

6
1 2 3 4 4

2 0
3 0
4 0
5 0
0 6
0 0

样例 3 解释

原始的树和转化的二叉树结构如下图：

6
1 2 3 4 3

2 0
3 0
4 0
5 6
0 0
0 0

样例 4 解释

原始的树和转化的二叉树结构如下图：

子任务

对于所有数据，保证 $n\le 10^6$，输入的树满足【题目描述】定义的有根有序树结构。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

本题输入量较大，请采用效率较高的读入方式。此外，C++ 默认的指针类型在本系统中为 64 位，可以使用 int 类型的数组下标（32 位）代替指针的作用，从而节省空间。

来源

清华 826 考研初试 2022 - 算法大题 背景介绍