#P18193. Tree Equation
Tree Equation
Tree Equation
DreamGrid 厌倦了求解普通的数学方程,开始研究有根树之间的方程。
对于一棵有根树 ,记它的根为 。定义两种运算:
- 加法:。将 与 的根合并为一个根 ,保留原来的所有边。也就是说, 和 的根的所有子树,都成为新根的子树。
- 乘法:。对于 中的每个顶点 ,取一份独立的 的副本,将副本的根与 合并。于是, 的根的所有子树都会各复制一份,成为 的新子树; 原来的边仍然保留。这里的“每个顶点”仅指原来属于 的顶点,不包含新复制出来的顶点。
下图展示了两种运算。注意,树的乘法一般不满足交换律。

给定三棵有根树 ,请找出两棵有根树 ,使得
这里的相等指有根无序树同构:只需树的结构和根相同,不要求顶点编号相同,兄弟节点没有顺序。
输入格式
第一行包含一个正整数 ,表示测试用例数。对于每个测试用例:
第一行包含三个整数 ,分别表示 的顶点数,满足
第二行包含 个整数 ,其中 表示 中第 个顶点的父亲,且 。
第三行以相同方式给出 的父亲数组 ;第四行给出 的父亲数组 。三棵输入树均保证是合法的有根树。父亲为 的顶点是根,因此根均为顶点 ,其余顶点的父亲均不为 。
所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,如果不存在满足等式的 ,输出一行 Impossible。
否则输出三行:
第一行输出两个整数 ,表示 的顶点数,满足 。
第二行输出 个整数 ,表示 的父亲数组,满足 。
第三行输出 个整数 ,表示 的父亲数组,满足 。
输出的 必须分别是一棵合法的有根树;父亲为 的顶点是根。若存在多组合法答案,输出任意一组。
样例 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