F. 重建二叉树

题目描述

给定一棵二叉树的先序遍历和中序遍历，请重建一棵以 1 号节点为根 的二叉树。

输入格式

第一行：$N$ 第二行：$P_1\ P_2\ \dots\ P_N$（先序遍历序列） 第三行：$I_1\ I_2\ \dots\ I_N$（中序遍历序列）

输出格式

如果无解输出 -1，否则第 $i$ 行输出节点 $i$ 的左右儿子，儿子为空则输出 0。

样例

输入样例 #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

输入样例 #2

2
2 1
1 2

输出样例 #2

-1

数据范围与提示

• $2 < N < 2 \times 10^5$
• $(P_1, P_2, \dots, P_N)$ 是 $(1, 2, \dots, N)$ 的排列
• $(I_1, I_2, \dots, I_N)$ 是 $(1, 2, \dots, N)$ 的排列