题目描述

我们需要计算怪物家族成员之间的基因关联度。每个怪物拥有相同数量的基因，但具体基因可能不同。已知：

1. 家族关系图（非树状结构）
2. 基因遗传规则：若怪物$C$是$A$和$B$的后代，则$C$的每个基因有$50\%$概率继承自$A$，$50\%$概率继承自$B$
3. 所有基因独立遗传

定义两个怪物$X$和$Y$的关联度为期望的相同基因比例（百分比）。例如：

• 完全无关的怪物$A$和$B$的后代$C$和$D$，其关联度为$50\%$
• 若$A$和$B$有关联，则$C$和$D$的关联度会更高

输入格式

• 第一行：$n$（怪物数量，$2 \leq n \leq 300$）和$k$（有父母的怪物数量，$0 \leq k \leq n-2$）
• 接下来$k$行：每行三个整数$a\ b\ c$，表示怪物$a$是$b$和$c$的后代
• 接下来一行：$m$（查询对数，$1 \leq m \leq n^2$）
• 接下来$m$行：每行两个整数，表示要查询的怪物编号

输出格式

输出$m$行，每行为一个百分比值（保留至小数点后两位，如$81.25\%$），表示对应怪物对的基因关联度。

样例输入

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%

题目来源

2002年西南欧地区竞赛