Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3990
Tree Equation

Time Limit: 3 Seconds      Memory Limit: 131072 KB      Special Judge

Tired of solving mathematical equations, DreamGrid starts to solve equations related to rooted trees.

Let \(A\) and \(B\) be two two arbitrary rooted trees and \(r(T)\) denotes the root of \(T\). DreamGrid has defined two basic operations:

  • Addition. \(T = A + B\) is built by merging the two roots \(r(A)\), \(r(B)\) into a new root \(r(T)\). That is the subtrees of \(A\) and \(B\) (if any) become the subtrees of \(r(T)\).
  • Multiplication. \(T = A \cdot B\) is built by merging \(r(B)\) with each vertex \(x \in A\) so that all the subtrees of \(r(B)\) become new subtrees of \(x\).

The following picture may help you understand the operations.

Given three rooted trees \(A\), \(B\) and \(C\), DreamGrid would like to find two rooted trees \(X\) and \(Y\) such that \(A \cdot X + B \cdot Y = C\).

Input

There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:

The first line contains three integers \(n_a\), \(n_b\) and \(n_c\) (\(2 \le n_a, n_b \le n_c \le 10^5\)) -- the number of vertices in rooted tree \(A\), \(B\) and \(C\), respectively.

The second line contains \(n_a\) integers \(a_1, a_2, \dots, a_{n_a}\) (\(0 \le a_i < i\)) -- where \(a_i\) is the parent of the \(i\)-th vertex in tree \(A\).

The third line contains \(n_b\) integers \(b_1, b_2, \dots, b_{n_b}\) (\(0 \le b_i < i\)) -- where \(b_i\) is the parent of the \(i\)-th vertex in tree \(B\).

The fourth line contains \(n_c\) integers \(c_1, c_2, \dots, c_{n_c}\) (\(0 \le c_i < i\)) -- where \(c_i\) is the parent of the \(i\)-th vertex in tree \(C\).

Note that if \(a_i=0\) (\(b_i=0\) or \(c_i=0\)), then the \(i\)-th vertex is the root of the tree \(A\) (\(B\) or \(C\)).

It is guaranteed that the sum of all \(n_c\) does not exceed \(2 \times 10^6\).

Output

For each test case, if you can not find a solution, output "Impossible" (without quotes) in the first line.

Otherwise, output two integers \(n_x\) and \(n_y\) (\(1 \le n_x, n_y \le 10^5\)) denoting the number of vertices in rooted tree \(X\) and \(Y\) in the first line.

Then in the second line, output \(n_x\) integers \(x_1, x_2, \dots, x_{n_x}\) (\(0 \le x_i < i\)) -- where \(x_i\) is the parent of the \(i\)-th vertex in tree \(X\).

Then in the third line, output \(n_y\) integers \(y_1, y_2, \dots, y_{n_y}\) (\(0 \le y_i < i\)) -- where \(y_i\) is the parent of the \(i\)-th vertex in tree \(Y\).

If there are multiple solutions, print any of them.

Sample Input

2
2 3 10
0 1
0 1 2
0 1 1 3 4 3 6 3 1 9
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9

Sample Output

Impossible
2 1
0 1
0

Author: LIN, Xi
Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site
Submit    Status