You may have heard the expression "the enemy of my enemy is my friend". By extension, then, "the enemy of my enemy of my enemy is my enemy", and so on. Given a set of relationships, you wish to determine how much of a friend or enemy people are, represented by a "total relationship score".
Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set will consist of a series of lines.
For each data set, print a single line containing the total relationship scores between the name given in the final line of the data set and every other person in the data set, with each score separated by a single space and in the same order that the names appear in the input. The total relationship score between two people is the sum total of all the relationship scores of direct and indirect relationships between them. Direct relationships are determined by the input described above. Indirect relationships are those in which a cycle-free path of two or more relationships can be traced between two people, with none of those relationships being of the neutral variety (e.g., an "enemy of an enemy" or an "enemy of a friend of an enemy"). The formula for determining a direct or indirect relationship score is as follows:
where x is the number of enemy relationships in the path and y is the total number of relationships in the path. Some examples follow:
Score = 128 × (−1)x 2(y-1)
Friend Score = 128 × (−1)0 ÷ 2(1-1) = 128Also note that the total relationship score of a person with themselves is 0.
Enemy Score = 128 × (−1)1 ÷ 2(1-1) = −128
Friend of a Friend Score = 128 × (−1)0 ÷ 2(2-1) = 64
Enemy of an Enemy Score = 128 × (−1)2 ÷ 2(2-1) = 64
Enemy of an Enemy of an Enemy Score = 128 × (−1)3 ÷ 2(3-1) = −32
3 5 Bob N F E N N Friend F N N N N Enemy E N N F E FriendOfEnemy N N F N N EnemyOfEnemy N N E N N Bob 4 Bob N F F F Tom F N E E Tim F E N F Joe F E F N Bob 4 Spy1 N E F N Spy2 E N E N Spy3 F E N N Spy4 N N N N Spy3
0 128 -128 -64 64 0 0 256 256 192 -192 0 0