当前没有测试数据。

F - 先序和中序

得分：500分

问题描述

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

判断是否存在以顶点$1$为根的二叉树，并给出这样的树（如果存在）。

• 树按照先序遍历的结果是$(P_1, P_2, \ldots, P_N)$。
• 树按照中序遍历的结果是$(I_1, I_2, \ldots, I_N)$。

约束条件

• $2\le{N}\le2\times10^5$
• $N$是整数。
• $(P_1, P_2, \ldots, P_N)$是$(1, 2, \ldots, N)$的一个排列。
• $(I_1, I_2, \ldots, I_N)$是$(1, 2, \ldots, 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

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

---

2
2 1
1 2

-1

不存在以顶点$1$为根的满足条件的二叉树，因此应打印$-1$。