← 返回题目列表

AtCoder · abc255_f

I. 预购和订购

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

考虑 二叉树 与 N 顶点编号 1, 2, \ldots, N。这里,二叉树是一个有根树,其中每个顶点最多有两个子节点。具体来说,二叉树中的每个顶点最多有一个 左孩子 并且最多一个 右孩子.

判断是否存在以Vertex为根的二叉树 1 满足以下条件,并呈现这样的树(如果存在)。

  • 中树的深度优先遍历 预购 is (P_1, P_2, \ldots, P_N).
  • 中树的深度优先遍历 按顺序 is (I_1, I_2, \ldots, I_N).

约束

  • 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 。