Score : $500$ points

问题陈述

考虑一个具有 $N$ 个顶点的 二叉树，顶点编号为 $1, 2, \ldots, N$。此处，二叉树是一个根树，其中每个顶点最多有两个子节点。具体来说，二叉树中的每个顶点至多有一个 左孩子 和至多有一个 右孩子。

确定是否存在一棵以顶点 $1$ 为根的二叉树满足以下条件，并在存在时给出这样的树。

• 该树按 前序遍历 的深度优先遍历序列为 $(P_1, P_2, \ldots, P_N)$。
• 该树按 中序遍历 的深度优先遍历序列为 $(I_1, I_2, \ldots, I_N)$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Consider a binary tree with $N$ vertices numbered $1, 2, \ldots, N$. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.

Determine whether there exists a binary tree rooted at Vertex $1$ satisfying the conditions below, and present such a tree if it exists.

• The depth-first traversal of the tree in pre-order is $(P_1, P_2, \ldots, P_N)$.
• The depth-first traversal of the tree in in-order is $(I_1, I_2, \ldots, I_N)$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $N$ is an integer.
• $(P_1, P_2, \ldots, P_N)$ is a permutation of $(1, 2, \ldots, N)$.
• $(I_1, I_2, \ldots, I_N)$ is a permutation of $(1, 2, \ldots, N)$.

Input

Input is given from Standard Input in the following format:

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

$I_1$ $I_2$ $\ldots$ $I_N$

Output

If there is no binary tree rooted at Vertex $1$ satisfying the conditions in Problem Statement, print $-1$.

Otherwise, print one such tree in $N$ lines as follows. For each $i = 1, 2, \ldots, N$, the $i$-th line should contain $L_i$ and $R_i$, the indices of the left and right children of Vertex $i$, respectively. Here, if Vertex $i$ has no left (right) child, $L_i$ ($R_i$) should be $0$.

If there are multiple binary trees rooted at Vertex $1$ satisfying the conditions, any of them will be accepted.

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

Sample Input 1

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

Sample Output 1

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

The binary tree rooted at Vertex $1$ shown in the following image satisfies the conditions.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

No binary tree rooted at Vertex $1$ satisfies the conditions, so $-1$ should be printed.

update @ 2024/3/10 10:52:11