Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
149 - The 2017 China Collegiate Programming Contest, Qinhuangdao Site - J
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

Submit    Status