By the definition of pre-order and in-order, \(P\) and \(I\) corresponding to the binary tree has the following property:

• \(P\) is a concatenation of root \(r\), the pre-order traversal \(P^L\) of the left subtree of \(r\), and the pre-order traversal \(P^R\) of the right subtree of \(r\), in this order.
• \(I\) is a concatenation of the in-order traversal \(I^L\) of the left subtree of \(r\), the root \(r\), and the in-order traversal \(I^R\) of the right subtree of \(r\), in this order.

The following figure illustrates the example corresponding to Sample Input 1.

We will now explain the solution to this problem. Suppose that there exists a binary tree satisfying the condition for the given \(P\) and \(I\). We will identify the binary tree using the property of \(P\) and \(I\) mentioned above. (In fact, the binary tree satisfying the conditions is unique.) Specifically, follow Step 1. through Step 6. below.

1. Identify the root \(r\) of the tree, which can be found as the first element of \(P\).
2. Find the position of \(r\) in \(I\).
3. Identify \(I^L\) and \(I^R\). The elements of \(I\) in the left of \(r\) form \(I^L\), and those in the right form \(I^R\).
4. Identify \(P^L\) and \(P^R\). The length of \(P^L\) is equal to that of \(I^L\). Since we already know the length of \(P^L\), we can identify which part corresponds to \(P^L\) and \(P^R\).
5. The first element of \(P^L\) is found to be the root of the left subtree of \(r\), that is, the left child of \(r\). Similarly, the first element of \(P^R\) is found to be the right child of \(r\). If \(P^L\) (or \(P^R\)) is empty, then \(r\) does not have a left (or right) child.
6. Then, regard segments \((P^L, I^L)\) (and segments \((P^R, I^R\)) as \((P, I)\) and recursive follow Step 1. through Step 6.

When solving a problem for subsegments \((P', I')\) of \(P\) and \(I\), it may occur in Step 2. that \(r\) is not contained in \(I'\). In that case, the assumption that there exists a binary tree for the given \(P\) and \(I\) is wrong, so print \(-1\) and terminate.

By implementing the procedure above properly, the problem can be solved in a total of \(\mathrm{O}(N)\) time.

Her are some notes on how to accomplish \(\mathrm{O}(N)\) time.

• When solving a subproblem on a subsegments \((P', I')\) of \(P\) and \(I\), you should not construct the subsegments \(P'\) and \(I'\) explicitly, because that will degrade the worst time complexity for this algorithm to \(\mathrm{\Theta}(N^2)\). Instead, it is a good idea to store only the both ends of \(P'\) and \(I'\) on the original \(P\) and \(I\).

In order to find the position of \(r\) in \(I\), you should not scan \(I\) naively every time, since that will degrade the worst time complexity to \(\mathrm{\Theta}(N^2)\). Instead, it is a good idea to “precalculate an array \(I^{-1}\) such that \(I^{-1}[I_r] = r\) for all \(r = 1, 2, \ldots, N\), and refer to it in every execution of Step 2. in an \(\mathrm{O}(1)\) time.

The following is a sample code in 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;
}