分数: 500 点
问题陈述
考虑 二叉树 与 N 顶点编号 1, 2, \ldots, N。这里,二叉树是一个有根树,其中每个顶点最多有两个子节点。具体来说,二叉树中的每个顶点最多有一个 左孩子 并且最多一个 右孩子.
判断是否存在以Vertex为根的二叉树 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).
输入
输入由标准输入按以下格式给出:
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,Vertex 左右子节点的索引
分别是 i。
这里,如果顶点 i 没有左(右)孩子, L_i (R_i)应该是 0.
如果有多个以 Vertex 为根的二叉树 1 满足条件,其中任何一个都将被接受。
L_1 R_1 L_2 R_2 \vdots L_N R_N
示例输入 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
以顶点为根的二叉树 下图中显示的 1 满足条件。

示例输入 2
2 2 1 1 2
示例输出 2
-1
没有以顶点为根的二叉树 1 满足条件,所以 -1 。