[AdditionalFile6983.zip](file://AdditionalFile6983.zip?type=additional_file)

#6983. 「ICPC World Finals 2025」歪斜的推理

标签: 传统 | 时间限制: 2000 ms | 内存限制: 2048 MiB |

题目描述

以下内容基于一个真实的故事——为了保护当事人，文中的姓名均已更换……嗯，毕竟在这种故事里，你总是得这么做。

Taylor Swift 教授正在批改一份关于整数斜堆的作业。斜堆是一种二叉树，每个节点存储一个整数，并且任何节点中的值都小于或等于其任意子节点中的值。请注意，斜堆不一定是完美二叉树；也就是说，任何节点的左子树和/或右子树都可以为空。

将值 $x$ 插入斜堆 $H$ 的过程通过以下递归步骤完成：

• 如果 $H$ 为空，则将 $H$ 变成一个只包含一个节点（值为 $x$）的斜堆。
• 否则，设 $y$ 为 $H$ 的根节点的值。
• 如果 $y<x$，交换根节点的两个子节点，然后将 $x$ 递归地插入到新的左子树中。
• 如果 $y \geq x$，创建一个值为 $x$ 的新节点，并将 $H$ 作为这个新节点的左子树。

图 A.1：将值 $7$ 插入斜堆的样例。存储 $4$ 和 $5$ 的节点（蓝色标记）的子节点被交换，而存储 $11$ 的节点则成为新插入节点（红色标记）的左子节点。

现在，让我们回到 Swift 教授的故事。她布置的作业题目是，给定一个从 $1$ 到 $n$ 的数字排列，要求学生们按照给定顺序将这些数字插入一个空堆中，并给出最终形成的堆。出人意料的是，有些学生给出了错误的答案！这让 Swift 教授开始思考：对于一个给定的堆，是否存在一个输入排列能够生成这个堆？如果存在，那么字典序最小和最大的输入排列分别是什么？

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^{5})$，表示树中的节点数量。这些节点恰好包含从 $1$ 到 $n$ 的数字。接下来是 $n$ 行，第 $i$ 行包含两个整数 $\ell_{i}$ 和 $r_{i}$（$i<\ell_{i} \leq n$ 或 $\ell_{i}=0$；$i<r_{i} \leq n$ 或 $r_{i}=0$），描述了存储值为 $i$ 的节点的左、右子节点的值。值为 $0$ 表示对应的子节点不存在。保证这些数据描述的是一棵二叉树。

输出格式

输出能够通过斜堆插入方法生成给定树的、字典序最小的输入排列，以及字典序最大的输入排列。这两个排列可能相同，此时仍需将它们都输出。如果不存在能够生成给定树的输入排列，则输出 impossible。

样例 1

输入

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

输出

1 3 2 7 5 6 4
7 1 5 3 2 6 4

样例 2

输入

2
0 2
0 0

输出

impossible

样例 3

输入

3
2 0
3 0
0 0

输出

2 3 1
3 2 1