题目描述

我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。

妖怪之间的基因继承关系相当简单：如果妖怪 $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\ (2 \le n \le 300)$ 和 $k$。表示家族中成员数，它们分别用 $1,2,\cdots,n$ 来表示。$k\ (0 \le k \le n-2)$ 表示这个家族中有父母的妖怪数量（其他的妖怪没有父母，它们之间可以认为毫无关系，即没有任何相同基因）。

接下来的 $k$ 行，每行三个整数 $a,b,c$，表示妖怪 $a$ 是妖怪 $b$ 的孩子。

然后是一行一个整数 $m$（$1 \le m \le n_2$），表示需要计算基因相似程度的妖怪对数。

接下来的 $m$ 行，每行两个整数，表示需要计算基因相似程度的两个妖怪。

你可以认为这里给出的家谱总是合法的。具体来说就是，没有任何的妖怪会成为自己的祖先，并且你也不必担心会存在性别错乱问题。

输出格式

共 $m$ 行。可 $k$ 行表示第 $k$ 对妖怪之间的基因相似程度。你必须按百分比输出，有多少精度就输出多少，而且必须准确，但不允许出现多余的 $0$（注意，$0.001$ 的情况应输出 $\verb!0.1$，而不是 $\verb!.1$）。具体格式参见样例。

7 4                                                    
4 1 2                                          
5 2 3                                          
6 4 5                                          
7 5 6
4
1 2
2 6
7 5
3 3

0%
50%
81.25%
100%