Welcome to ZOJ
 Problem Sets 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$.

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