/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
1, 2, \ldots, N と番号づけられた N 個の頂点を持つ二分木を考えます。 ここで、二分木とは各頂点が高々 2 個の子を持つ根付き木です。より具体的には、二分木の各頂点は高々 1 個の左の子と高々 1 個の右の子を持ちます。
頂点 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) の順列
入力
入力は以下の形式で標準入力から与えられる。
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
6 1 3 5 6 4 2 3 5 1 4 6 2
出力例 1
3 6 0 0 0 5 0 0 0 0 4 2
次の画像に示す、頂点 1 を根とする二分木が問題文中の条件を満たします。
入力例 2
2 2 1 1 2
出力例 2
-1
問題文中の条件を満たすような頂点 1 を根とする二分木は存在しません。よって -1 を出力します。
Score : 500 points
Problem Statement
Consider a binary tree with N vertices numbered 1, 2, \ldots, N. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.
Determine whether there exists a binary tree rooted at Vertex 1 satisfying the conditions below, and present such a tree if it exists.
Constraints
- 2 \leq N \leq 2 \times 10^5
- N is an integer.
- (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
- (I_1, I_2, \ldots, I_N) is a permutation of (1, 2, \ldots, N).
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N I_1 I_2 \ldots I_N
Output
If there is no binary tree rooted at Vertex 1 satisfying the conditions in Problem Statement, print -1.
Otherwise, print one such tree in N lines as follows.
For each i = 1, 2, \ldots, N, the i-th line should contain L_i and R_i, the indices of the left and right children of Vertex i, respectively.
Here, if Vertex i has no left (right) child, L_i (R_i) should be 0.
If there are multiple binary trees rooted at Vertex 1 satisfying the conditions, any of them will be accepted.
L_1 R_1 L_2 R_2 \vdots L_N R_N
Sample Input 1
6 1 3 5 6 4 2 3 5 1 4 6 2
Sample Output 1
3 6 0 0 0 5 0 0 0 0 4 2
The binary tree rooted at Vertex 1 shown in the following image satisfies the conditions.
Sample Input 2
2 2 1 1 2
Sample Output 2
-1
No binary tree rooted at Vertex 1 satisfies the conditions, so -1 should be printed.