Pre-order and In-order

题目描述

考虑一个有 $N$ 个顶点、顶点编号为 $1, 2, \ldots, N$ 的 二叉树。这里，二叉树是以某个顶点为根的树，每个顶点最多有两个子节点。具体来说，二叉树中的每个顶点最多有一个 左子节点 并且最多有一个 右子节点。 判断是否存在一棵以顶点 $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$ 行应包含 $L_i$ 和 $R_i$，分别表示顶点 $i$ 的左子节点和右子节点的编号。 如果顶点 $i$ 没有左（右）子节点，则 $L_i$（$R_i$）应为 $0$.
如果存在多棵以顶点 $1$ 为根且满足条件的二叉树，输出其中任意一棵都将被接受。 $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

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

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

2
2 1
1 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$ 为根的二叉树，因此应输出 $-1$.

标签: AtCoder|abc255F

来源

AtCoder|abc255F