AT_abc255_f [ABC255F] Pre-order and In-order

[problemUrl]: https://atcoder.jp/contests/abc255/tasks/abc255_f $ 1,\ 2,\ \ldots,\ N $ と番号づけられた $ N $ 個の頂点を持つ**二分木**を考えます。 ここで、二分木とは各頂点が高々 $ 2 $ 個の子を持つ根付き木です。より具体的には、二分木の各頂点は高々 $ 1 $ 個の**左の子**と高々 $ 1 $ 個の**右の子**を持ちます。 頂点 $ 1 $ を根とする二分木であって、下記の条件を満たすものが存在するかを判定し、存在する場合はその一例を示してください。 - すべての頂点を深さ優先探索における[**行きがけ順**](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)#.E6.B7.B1.E3.81.95.E5.84.AA.E5.85.88.E6.8E.A2.E7.B4.A2)（pre-order）で並べた列が $ (P_1,\ P_2,\ \ldots,\ P_N) $ である。 - すべての頂点を深さ優先探索における[**通りがけ順**](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)#.E6.B7.B1.E3.81.95.E5.84.AA.E5.85.88.E6.8E.A2.E7.B4.A2)（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 $

### 制約 - $ 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 $ を根とする二分木が問題文中の条件を満たします。 !\[\](https://img.atcoder.jp/abc255/b51399e8953ae1723d1d9e83617f9be9.png) ### Sample Explanation 2 問題文中の条件を満たすような頂点 $ 1 $ を根とする二分木は存在しません。よって $ -1 $ を出力します。