配点 : $500$ 点

問題文

$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)$ である。

制約

• $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$ 行目には頂点 $i$ の左の子の番号 $L_i$ と右の子の番号 $R_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$ を出力します。