妖怪之间的基因继承关系相当简单：如果妖怪 C 是妖怪 A 和 B 的孩子，则 C 的任意一个基因只能是继承 A 或 B 的基因，继承 A 或 B 的概率各占 50\%。所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。
现在，我们来定义两个妖怪X和Y的基因相似程度。例如，有一个家族，这个家族中有两个毫无关系(没有相同基因)的妖怪 A 和 B，及它们的孩子 C和 D。那么 C和 D相似程度是多少呢?因为 C和 D的基因都来自 A和 B，从概率来说，各占 50\%所以，依概率计算 C 和 D 平均有 50\% 的相同基因，C 和 D 的基因相似程度为 50\% 需要注意的是，如果 A 和 B 之间存在相同基因的话，C 和 D 的基因相似程度就不再是 50\% 了。
你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。
输入
第一行两个整数 n 和 k。n (2\leq n\leq 300) 表示家族中成员数，它们分别用 1，2，…，n 来表示。k (0\leq k\leq n-2)表示这个家族中有父母的妖怪数量(其他的妖怪没有父母，它们之间可以认为毫无关系，即没有任何相同基因)。
接下来的 k 行，每行三个整数 a，b，c，表示妖怪 a 是妖怪 b 和 c 的孩子。
然后是一行一个整数 m (1\leq m\leq n^{2})，表示需要计算基因相似程度的妖怪对数。
接下来的 m 行，每行两个整数，表示需要计算基因相似程度的两个妖怪。
你可以认为这里给出的家谱总是合法的。具体来说就是，没有任何的妖怪会成为自己的祖先，并且你也不必担心会存在性别错乱问题。
输出
共 m 行。第 k 行表示第 k 对妖怪之间的基因相似程度。你必须按百分比输出，有多少精度就输出多少，但不允许出现多余的 0(注意，0.001 的情况应输出 0.1\%，而不是 .1\%)。具体格式参见样例。