二分木に対応する \(P\) と \(I\) は、行きがけ順および通りがけ順の定義より、下記の性質をもちます。

• \(P\) は、根 \(r\) 、\(r\) の左部分木の頂点を行きがけ順に並べた列 \(P^L\) 、\(r\) の右部分木の頂点を行きがけ順に並べた列 \(P^R\) をこの順に連結した列である。
• \(I\) は、\(r\) の左部分木の頂点を通りがけ順に並べた列 \(I^L\) 、根 \(r\) 、\(r\) の右部分木の頂点を通りがけ順に並べた列 \(I^R\) をこの順に連結した列である。

入力例 1 に対応する例を下の図に示します。

本問題の解法を以下に述べます。 与えられた \(P\) と \(I\) に対して条件を満たす二分木が存在すると仮定し、上記の \(P\) と \(I\) の性質を利用して、その二分木を特定していきます。（実は、条件を満たす二分木は、存在するならば唯一です。） 具体的には下記の手順 1. から手順 6. を行います。

1. 木の根 \(r\) を特定します。これには \(P\) の先頭要素を見れば良いです。
2. \(I\) の中で \(r\) が出現する位置を求めます。
3. \(I^L\) と \(I^R\) を特定します。 \(I\) のうち \(r\) より左側の部分が \(I^L\) 、右側の部分が \(I^R\) だと特定できます。
4. \(P^L\) と \(P^R\) を特定します。 \(P^L\) の長さは \(I^L\) の長さと等しいです。\(P^L\) の長さがわかるので、\(P\) の中でどこが \(P^L\) の部分で \(P^R\) の部分かを特定できます。
5. \(P^L\) の先頭要素が \(r\) の左部分木の根、すなわち、\(r\) の左の子とわかります。同様に、\(P^R\) の先頭要素が \(r\) の右の子とわかります。ただし、\(P^L\) （または \(P^R\) ）が空列の場合は \(r\) は左（または右）の子を持ちません。
6. その後、区間 \(P^L, I^L\) （および区間 \(P^R, I^R\) ）を再び \(P, I\) とみなして再帰的に手順 1. から手順 6. を行います。

\(P, I\) のある区間 \(P', I'\) に関する小問題を再帰的に解く際、手順 2. において \(r\) が \(I'\) の中に存在しないということが起こり得ます。 その場合、与えられた \(P\) と \(I\) に対して条件を満たす二分木が存在すると仮定したことが誤りであったことになるため、\(-1\) を出力して終了します。

上記の手順を適切に実装することで、\(\mathrm{O}(N)\) 時間で本問題を解くことができます。

以下に、\(\mathrm{O}(N)\) 時間で動作するように実装するための注意点を挙げます。

• \(P, I\) のある区間 \(P', I'\) に関する小問題を再帰的に解く際、対象の区間 \(P', I'\) をその都度陽に構築すると、アルゴリズム全体の最悪時間計算量は \(\mathrm{\Theta}(N^2)\) となります。 代わりに、対象区間 \(P', I'\) の \(P, I\) 上における左端と右端の位置のみを保持すると良いでしょう。

• 上記の手順 2. で \(I\) の中の \(r\) の位置を探すために、その都度 \(I\) を愚直に走査するとアルゴリズム全体の最悪時間計算量は \(\mathrm{\Theta}(N^2)\) となります。代わりに、各頂点の \(I\) 上での位置を記録した配列、すなわち、「すべての \(r = 1, 2, \ldots, N\) について \(I^{-1}[I_r] = r\) 」を満たす配列 \(I^{-1}\) をあらかじめ前計算しておき、手順 2. を行うたびに \(\mathrm{O}(1)\) 時間でこれを参照すると良いでしょう。

以下に C++ 言語による正解例を記載します。

#include <iostream>
using namespace std;

int n;
int P[200005], I[200005], Iinv[200005];
int L[200005], R[200005];

bool solve(int s, int t, int S, int T)
{
  int r = P[s], p = Iinv[r];
  if(p < S || T < p) return false;

  if(p-S > 0){
    L[r] = P[s+1];
    if(!solve(s+1, s+p-S, S, p-1)) return false;
  }
  if(T-p > 0){
    R[r] = P[s+p-S+1];
    if(!solve(s+p-S+1, t, p+1, T)) return false;
  }
  return true;
}

int main(void)
{
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> P[i];
  for(int i = 1; i <= n; i++) cin >> I[i];
  for(int i = 1; i <= n; i++) Iinv[I[i]] = i;

  if(P[1] != 1 || !solve(1, n, 1, n)){
    cout << -1 << endl;
    return 0;
  }
  for(int i = 1; i <= n; i++) cout << L[i] << " " << R[i] << endl;

  return 0;
}