AT_abc255_f [ABC255F] Pre-order and In-order

题目描述

考虑一棵有 $N$ 个顶点、编号为 $1, 2, \ldots, N$ 的二叉树。这里，二叉树指的是每个顶点最多有 $2$ 个子节点的有根树。更具体地说，二叉树中的每个顶点最多有 $1$ 个左子节点和最多 $1$ 个右子节点。

请判断是否存在以顶点 $1$ 为根的二叉树，满足以下条件，并在存在时给出一个例子。

• 用深度优先搜索的先序遍历得到的所有顶点的排列为 $(P_1, P_2, \ldots, P_N)$。
• 用深度优先搜索的中序遍历得到的所有顶点的排列为 $(I_1, I_2, \ldots, I_N)$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $I_1$ $I_2$ $\ldots$ $I_N$

输出格式

如果不存在满足题目条件、以顶点 $1$ 为根的二叉树，则输出 $-1$。
如果存在，请输出满足条件的二叉树的一个例子，按照如下格式输出 $N$ 行。即，对于 $i = 1, 2, \ldots, N$，第 $i$ 行输出顶点 $i$ 的左子节点编号 $L_i$ 和右子节点编号 $R_i$。如果没有左子节点（或右子节点），则 $L_i$（或 $R_i$）输出 $0$。
如果存在多个满足条件的以顶点 $1$ 为根的二叉树，输出其中任意一个均可。

$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输入输出样例 #1

输入 #1

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

输出 #1

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

输入输出样例 #2

输入 #2

2
2 1
1 2

输出 #2

-1

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $N$ 是整数
• $(P_1, P_2, \ldots, P_N)$ 是 $(1, 2, \ldots, N)$ 的一个排列
• $(I_1, I_2, \ldots, I_N)$ 是 $(1, 2, \ldots, N)$ 的一个排列

样例解释 1

如下图所示，以顶点 $1$ 为根的二叉树满足题目中的条件。

样例解释 2

不存在满足题目条件、以顶点 $1$ 为根的二叉树。因此输出 $-1$。

由 ChatGPT 4.1 翻译