Family

We want to measure how closely related the members of a family of monsters are. Every monster has the same number of genes, but individual genes may differ from monster to monster. It would be useful to know how many genes any two monsters share, but counting directly is impossible because the number of genes is enormous. However, we know the family graph (which is not exactly a tree) and how genes are inherited, so we can compute the expected number of shared genes precisely.

The inheritance rule is simple: if monster $C$ is a child of monsters $A$ and $B$, then each gene of $C$ is identical to the corresponding gene of $A$ or of $B$, each with probability $50%$ (independently for every gene). Every gene of every monster is inherited independently.

Define the degree of relationship of monsters $X$ and $Y$ as the expected number of shared genes. For example, consider a family of two completely unrelated monsters $A$ and $B$ (they share no genes) and their two children $C$ and $D$. Each gene of $C$ comes from $A$ or $B$ with probability $50%$ each, and the same holds for $D$. Hence a given gene of $C$ matches the corresponding gene of $D$ with probability $50%$, so the degree of relationship of $C$ and $D$ is $50%$ of all genes. The answer would differ if $A$ and $B$ were related, because any genes shared by $A$ and $B$ would necessarily be inherited by both $C$ and $D$.

Given a family graph and a list of monster pairs, compute the degree of relationship for each pair. Your program must:

• read the description of a family and a list of member pairs from standard input,
• compute the degree of relationship (as a percentage) for each pair,
• write the results to standard output.

The first line contains two integers $n$ and $k$ separated by a single space. $n$ ($2 \le n \le 300$) is the number of family members, numbered arbitrarily from $1$ to $n$. $k$ ($0 \le k \le n-2$) is the number of monsters that have parents; every other monster was created by the gods and is completely unrelated to the others.

Each of the next $k$ lines contains three distinct integers $a$, $b$, $c$ separated by single spaces, meaning that monster $a$ is a child of monsters $b$ and $c$.

The next line contains an integer $m$ ($1 \le m \le n^2$), the number of pairs. Each of the next $m$ lines contains two integers: the numbers of two monsters.

No monster is its own ancestor. You should make no additional assumptions about the input data; in particular, do not assume that any valid assignment of sexes exists.

Output $m$ lines. The $i$-th line corresponds to the $i$-th pair and contains that pair's exact degree of relationship as a percentage, followed by a percent sign (%). Do not print insignificant zeros; however, there must be at least one digit before the decimal point (for example, the leading zero in $0.1$ is significant and must not be written as .1). The exact value is always a finite decimal.