题目描述

我们正在研究妖怪家族的血缘关系。

每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。

我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。

由于基因数量相当庞大，直接检测是行不通的。

但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。

妖怪之间的基因继承关系相当简单：如果妖怪$\red C$是妖怪$\red A$和$\red B$的孩子，则$\red C$的任意一个基因只能是继承$\red A$或$\red B$的基因，继承$\red A$或$\red B$的概率各占$\red {50％}$。

所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。

现在，我们来定义两个妖怪$\red X$和$\red Y$的基因相似程度。

例如，有一个家族，这个家族中有两个毫无关系(没有相同基因)的妖怪$\red A$和$\red B$，及它们的孩子$\red C$和$\red D$。

那么$\red C$和$\red D$相似程度是多少呢?因为$\red C$和$\red D$的基因都来自$\red A$和$\red B$，从概率来说，各占$\red {50％}$。

所以，依概率计算$\red C$和$\red D$平均有$\red {50％}$的相同基因，$\red C$和$\red D$的基因相似程度为$\red {50％}$。

需要注意的是，如果$\red A$和$\red B$之间存在相同基因的话，$\red C$和$\red D$的基因相似程度就不再是$\red {50％}$了。

你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。

输入格式

第一行两个整数$\red n$和$\red k$。

$\red {n(2≤n≤300)}$表示家族中成员数，它们分别用$\red {1，2，…，n}$来表示。

$\red {k(0≤k≤n-2)}$表示这个家族中有父母的妖怪数量(其他的妖怪没有父母，它们之间可以认为毫无关系，即没有任何相同基因)。

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

然后是一行一个整数$\red {m(1≤m≤n^2)}$，表示需要计算基因相似程度的妖怪对数。

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

你可以认为这里给出的家谱总是合法的。

具体来说就是，没有任何的妖怪会成为自己的祖先，并且你也不必担心会存在性别错乱问题。

输出格式

共$\red m$行。

第$\red k$行表示第$\red k$对妖怪之间的基因相似程度。

你必须按百分比输出，有多少精度就输出多少，但不允许出现多余的$\red 0$(注意，$\red {0.001}$的情况应输出$\red {0.1％}$，而不是$\red {.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％