SP115 FAMILY - Family

我们想知道怪物家族的成员之间有多大的关联。每个怪物都有相同数量的基因，但每个怪物的基因本身可能不同。如果能知道任意两个怪物有多少共同的基因，那就太好了。然而，这是不可能的，因为基因的数量非常大。不过，我们确实知道家谱（其实不是一棵树，但你不能真的责怪他们，这些都是怪物，对吧？）我们确实知道这些基因是如何遗传的，所以我们可以很好地估计常见基因的数量。 遗传规则非常简单：如果怪物C是怪物a和B的后代，那么C的每个基因都与a或B的相应基因相同，每个基因的概率为50%。每个怪物的每个基因都是独立遗传的。 让我们定义怪物X和Y之间的关系程度为共同基因的预期数量。例如，考虑一个由两个完全不相关（即没有共同基因）的怪物a和B及其两个孩子C和D组成的家庭。C和D有多少相关？C的每个基因要么来自A要么来自B，概率都是50%。D也是如此。因此，给定的C基因与相应的D基因相同的概率为50%。因此，C和D（共同基因的预期数量）的关联度等于所有基因的50%。请注意，如果A和B是相关的，答案会有所不同。因为如果A和B有共同的基因，那么C和D必然都会遗传这些基因。 你的任务是编写一个程序，给定一个族图和一组怪物对，计算每对怪物的关系程度。 任务 编写一个程序： - 从标准输入中读取族的描述及其成员对的列表。 - 计算列表中每一对的关系程度（百分比）。 - 将结果写入标准输出。

输入以整数 $t$ 开始，即测试用例的数量。然后，$t$ 组测试用例随之出现。 对于每个测试用例，输入的第一行包含由单个空格分隔的两个整数 $n$ 和 $k$ 。整数 $n$ $（2 \leqslant n \leqslant 300）$是一个家庭中的成员数。家庭成员从 $1$ 到 $n$ 任意编号。整数 $k（0\leqslant k \leqslant n-2）$ 是有父母的怪物数量（所有其他怪物都是神创造的，彼此完全无关）。 接下来的k行中的每一行都包含三个不同的整数 $a、b、c$ ，它们之间用单个空格分隔。这意味着怪物 $a$ 是怪物 $ b$ 和 $c$ 的后代。 下一个输入行包含一个整数$ m $ $（1 \leqslant m \leqslant n^{2}）$ ——列表中怪物对的数量。接下来的m行中的每一行都包含两个由一个空格分隔的整数——这是两个怪物的数字。 你可以假设没有怪物是自己的祖先。你不应该对输入数据做任何额外的假设。特别是，你不应该假设存在任何有效的性别分配。

对于每个测试用例，输出由 $m$ 行组成。第 $i$ 行对应于列表中的第 $i$ 对，应该包含一个数字，后跟百分号。数字应该是第 $i$ 对中怪物的确切关系程度（百分比形式）。输出中不允许使用无符号零（但请注意，句号前必须至少有一位数字，例如数字 $0.1$ 中的前导零是有效的，您不能将其打印为 $.1$ ）。