FAMILY - Family

We want to find out how much related are the members of a family of monsters. Each monster has the same number of genes but the genes themselves may differ from monster to monster. It would be nice to know how many genes any two given monsters have in common. This is impossible, however, since the number of genes is very large. Still, we do know the family tree (well, not actually a tree, but you cannot really blame them, these 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 different if A and B were related. For if A and B had common genes, these would be necessarily inherited by both C and D.

Your task is to write a program that, given a family graph and a list of pairs of monsters, computes the degree of relationship for each of these pairs.

Task

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 input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first line of the input contains two integers n and k separated by a single space. Integer n (2 <= n <= 300) is the number of members in a family. Family members are numbered 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 different 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 numbers of two monsters.

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.

Output

For each test case the output consists of m lines. The i-th line corresponds to the i-th pair on the 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. Unsignificant 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). Confront the example output for the details of the output format.

Example

Sample input:
1
7 4
4 1 2
5 2 3
6 4 5
7 5 6
4
1 2
2 6
7 5
3 3

Sample output:
0%
50%
81.25%
100%
Warning: large Input/Output data, be careful with certain languages

Added by:adrian
Date:2004-07-07
Time limit:15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:ACM Central European Programming Contest, Warsaw 2002

hide comments
2018-10-19 21:19:36 :D
The issue here is that explaining it also spoils the problem a little. Wrapping your head around the the relationship formulas is a part of the solution.
2017-07-26 15:17:29 Sigma Kappa
Yes, I second @Ayush Mishra. According to my understanding of the problem, it should be 43.75%.

EDIT: But wait, since 5 is a direct parent of 6, and 7 is 5 and 6-s child, then 81% seems reasonable. So, I need some better model.... Excellent problem...

Last edit: 2017-07-26 15:21:48
2015-05-04 23:10:02 Ayush Mishra
Can anyone explain me the third test case?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.