P14280 [ICPC 2025 WF] A-Skew-ed Reasoning

以下故事基于真实事件——嗯，其中姓名已作修改，毕竟这类故事总是要改名字的。 Taylor Swift 教授正在批改一份关于整数斜堆（skiff heap）的作业。斜堆是一种二叉树，每个节点存储一个整数，且任意节点的值都小于或等于其所有子节点的值。注意斜堆不必是完全二叉树；也就是说，任意节点的左子树和（或）右子树可能为空。 将值 $ x $ 插入斜堆 $ H $ 的递归过程如下： - 如果 $ H $ 为空，则将 $ H $ 变为仅包含一个值为 $ x $ 的节点的斜堆。 - 否则，设 $ y $ 为 $ H $ 根节点的值。 - 如果 $ y < x $，则交换根节点的两个子树，并将 $ x $ 递归插入新的左子树。 - 如果 $ y \ge x $，则创建一个值为 $ x $ 的新节点，并将 $ H $ 作为该新节点的左子树。  图 A.1：将值 $7$ 插入斜堆的示例。存储值 4 和 5 的节点（蓝色标记）交换了它们的子节点，而存储值 $11$ 的节点成为新插入节点（红色标记）的左子节点。 现在回到 Swift 教授的故事。她布置的作业要求学生展示将数字 $ 1 $ 到 $ n $ 的某个给定排列按给定顺序依次插入空堆后得到的堆结构。令人惊讶的是，有些学生的答案是错误的！这让 Swift 教授思考：对于一个给定的堆，是否存在一个输入排列能够生成这个堆？如果存在，字典序最小和最大的输入排列分别是什么？

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

输出在斜堆插入方法下能够产生给定树的字典序最小的输入排列，然后是字典序最大的输入排列。这两个排列可能相同，如果相同你仍然需要输出两者。如果不存在能够产生给定树的输入排列，输出 `impossible`。