We want to find out how much are the members of a family of monsters related. Each monster has the same number of genes but the genes themselves may dier from monster to monster. It would be nice to know how many genes any two given monsters have in common. However this is impossible, because the number of genes is very large. Fortunately, we do know the family tree (well, not actually a tree, but you cannot really blame them, after all they are monsters, right?) and we do know how the genes are inherited so we can estimate the number of common genes quite well. The inheritance rule is very simple: if a monster C is a child of monsters A and B then each gene of C is identical to the corresponding gene of either A or B, each with probability 50%. Every gene of every monster is inherited independently. Let us define the degree of relationship of monsters X and Y as the expected number of common genes. For example consider a family consisting of two completely unrelated (i.e. having no common genes) monsters A and B and their two children C and D. How much are C and D related? Well, each of C’s genes comes either from A or from B, both with probability 50%. The same is true for D. Thus, the probability of a given gene of C being the same as the corresponding gene of D is 50%. Therefore the degree of relationship of C and D (the expected number of common genes) is equal to 50% of all the genes. Note that the answer would be dierent if A and B were related. If A and B have common genes they will be always inherited by both C and D. Your task is to write a program that, when given a family graph and a list of pairs of monsters, computes the degree of relationship for each of these pairs. Write a program that: • reads the description of a family and a list of pairs of its members from the standard input, • computes the degree of relationship (in percentages) for each pair on the list, • writes the result to the standard output. Input The first line of the input contains an integer indicating the number of data sets, followed by a blank line. The first line of each dataset contains two integers n and k separated by a single space. Integer n (2 ≤ n ≤ 300) is the number of members of a family. Family members are indexed arbitrarily from 1 to n. Integer k (0 ≤ k ≤ n − 2) is the number of monsters that do have parents (all the other monsters were created by Gods and are completely unrelated to each other). Each of the next k lines contains three dierent integers a, b, c separated by single spaces. The triple a, b, c means that the monster a is a child of monsters b and c. The next input line contains an integer m (1 ≤ m ≤ n2) — the number of pairs of monsters on the list. Each of the next m lines contains two integers separated by a single space — these are the indices of two monsters. Datasets are separated by a blank line. You may assume that no monster is its own ancestor. You should not make any additional assumptions on the input data. In particular, you should not assume that there exists any valid sex assignment.
2/2 Output The output for each dataset consists of m lines. The i-th line corresponds to the i-th pair on the input list and should contain single number followed by the percentage sign. The number should be the exact degree of relationship (in percentages) of the monsters in the i-th pair. Insignificant zeroes are not allowed in the output (please note however that there must be at least one digit before the period sign so for example the leading zero in number 0.1 is significant and you cannot print it as .1). Consult the example output for the details of the output format. Print a blank line between data sets. Sample Input 1 74 412 523 645 756 4 12 26 75 33 Sample Output 0% 50% 81.25% 100%