前序与中序

题目描述

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

判断是否存在一棵以顶点 1 为根、满足以下条件的二叉树，如果存在，请给出其中一棵。

• 所有顶点按深度优先搜索的前序（pre-order）遍历排列为 $(P_1, P_2, \ldots, P_N)$。
• 所有顶点按深度优先搜索的中序（in-order）遍历排列为 $(I_1, I_2, \ldots, I_N)$。

输入格式

输入按以下格式从标准输入给出：

N
P_1 P_2 … P_N
I_1 I_2 … 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
⋮
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

存在一棵以顶点 1 为根、满足题目条件的二叉树。

2
2 1
1 2

-1

不存在满足条件的以顶点 1 为根的二叉树，因此输出 $-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)$ 的排列。

提示

答案不唯一，输出任意合法解即可。