时间限制： 1.0 秒

空间限制： 64 MB

题目背景

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

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

题目描述

在本题中你需要将一个按照“长子-兄弟表示法”表示一般树的二叉树还原为原本的有根有序树形式。

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

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

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

输入格式

从标准输入读入数据。

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

接下来 $n$ 行，每行两个整数，分别表示转化的二叉树当中， $i$ 号节点的左子节点和右子节点的编号。特殊地，若其左/右子节点不存在，则对应位置为 $0$。

输出格式

输出到标准输出。

输出一行 $n-1$ 个正整数，相邻整数之间用一个空格分隔，分别表示还原的一般树中，$2\sim n$ 号节点的父亲。

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

1 1 3 3 1

样例 1 解释

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

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

1 2 3 4 5

样例 2 解释

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

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

1 2 3 4 4

样例 3 解释

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

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

1 2 3 4 3

样例 4 解释

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

子任务

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

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

提示

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

来源

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