题目描述

$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$ $\ldots$ $P_N$ $I_1$ $I_2$ $\ldots$ $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$ $\vdots$ $L_N$ $R_N$

题目大意

给定一棵二叉树的先序遍历和中序遍历，请构造一棵以 $1$ 节点为根的二叉树。第 $i$ 行输出节点 $i$ 的左右儿子，儿子为空则输出 $0$。无解输出 -1。

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

2
2 1
1 2

-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)$ の順列

Sample Explanation 1

次の画像に示す、頂点 $1$ を根とする二分木が問題文中の条件を満たします。 

Sample Explanation 2

問題文中の条件を満たすような頂点 $1$ を根とする二分木は存在しません。よって $-1$ を出力します。