#P18193. Tree Equation

Tree Equation

Tree Equation

DreamGrid 厌倦了求解普通的数学方程,开始研究有根树之间的方程。

对于一棵有根树 TT,记它的根为 r(T)r(T)。定义两种运算:

  • 加法:T=A+BT=A+B。将 AA 与 BB 的根合并为一个根 r(T)r(T),保留原来的所有边。也就是说,AA 和 BB 的根的所有子树,都成为新根的子树。
  • 乘法:T=A⋅BT=A\cdot B。对于 AA 中的每个顶点 xx,取一份独立的 BB 的副本,将副本的根与 xx 合并。于是,BB 的根的所有子树都会各复制一份,成为 xx 的新子树;AA 原来的边仍然保留。这里的“每个顶点”仅指原来属于 AA 的顶点,不包含新复制出来的顶点。

下图展示了两种运算。注意,树的乘法一般不满足交换律。

树的加法与乘法,图中依次为 A、B、A+B、A·B 和 B·A

给定三棵有根树 A,B,CA,B,C,请找出两棵有根树 X,YX,Y,使得

A⋅X+B⋅Y=C.A\cdot X+B\cdot Y=C.

这里的相等指有根无序树同构:只需树的结构和根相同,不要求顶点编号相同,兄弟节点没有顺序。

输入格式

第一行包含一个正整数 TT,表示测试用例数。对于每个测试用例:

第一行包含三个整数 na,nb,ncn_a,n_b,n_c,分别表示 A,B,CA,B,C 的顶点数,满足

2≤na,nb≤nc≤105.2\le n_a,n_b\le n_c\le 10^5.

第二行包含 nan_a 个整数 a1,a2,…,anaa_1,a_2,\ldots,a_{n_a},其中 aia_i 表示 AA 中第 ii 个顶点的父亲,且 0≤ai<i0\le a_i<i。

第三行以相同方式给出 BB 的父亲数组 b1,b2,…,bnbb_1,b_2,\ldots,b_{n_b};第四行给出 CC 的父亲数组 c1,c2,…,cncc_1,c_2,\ldots,c_{n_c}。三棵输入树均保证是合法的有根树。父亲为 00 的顶点是根,因此根均为顶点 11,其余顶点的父亲均不为 00。

所有测试用例的 ncn_c 之和不超过 2×1062\times10^6。

输出格式

对于每个测试用例,如果不存在满足等式的 X,YX,Y,输出一行 Impossible。

否则输出三行:

第一行输出两个整数 nx,nyn_x,n_y,表示 X,YX,Y 的顶点数,满足 1≤nx,ny≤1051\le n_x,n_y\le10^5。

第二行输出 nxn_x 个整数 x1,x2,…,xnxx_1,x_2,\ldots,x_{n_x},表示 XX 的父亲数组,满足 0≤xi<i0\le x_i<i。

第三行输出 nyn_y 个整数 y1,y2,…,ynyy_1,y_2,\ldots,y_{n_y},表示 YY 的父亲数组,满足 0≤yi<i0\le y_i<i。

输出的 X,YX,Y 必须分别是一棵合法的有根树;父亲为 00 的顶点是根。若存在多组合法答案,输出任意一组。

样例 1

输入:

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

输出:

Impossible
2 1
0 1
0

样例 2

输入:

1
5 5 49
0 1 1 3 1
0 1 2 1 2
0 1 2 3 4 1 6 7 8 9 1 11 12 13 14 11 16 17 18 19 1 21 22 23 24 1 26 26 1 1 30 31 31 30 30 35 36 36 35 30 40 41 41 40 1 45 46 46 45

输出:

5 5
0 1 2 3 4
0 1 1 3 3