
ZOJ Problem Set  3990
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:
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\). InputThere 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\). OutputFor 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 Input2 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 OutputImpossible 2 1 0 1 0 Author: LIN, Xi Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site 