Family Trees

Nowadays New Zealanders come from a variety of backgrounds. One person's ancestry can mix contributions from Maori, the Pacific Islands, several western European nations, and quite possibly some south east Asia as well. Given a suitable database of family lineages, working out those proportions for one person looks reasonably simple. The world has never been simple, though, so for a given pair of people all we can really determine is how much the earlier one contributed to the later one, if anything at all. Write a program that does this.

Everyone inherits exactly half of their ancestry from each listed parent. The share an ancestor contributes to a descendant is therefore the sum of $(1/2)^k$ over every line of descent that connects the two, where $k$ is the number of generations along that line.

The input is a series of family trees, each one followed by queries about that tree.

A family tree is a series of lines that ends with a line holding a single #. Each line holds three different names separated by spaces: a person, then his or her two parents. A name has fewer than 20 letters. No name appears in the first position more than once, so everyone has either zero or two listed parents, and there are no cycles, so no one is their own ancestor.

The queries follow, and they also end with a line holding a single #. Each query is a pair of names that may or may not appear in the family tree.

A line holding a single # ends the input.

Print one line for each query.

If one of the two people named in a query is a descendant of the other, print the name of the descendant, a space, the word is, a space, the share of ancestry in lowest terms, a space, the name of the ancestor, and then a full stop ..

Otherwise print A and B are not related. with the two names in the order they were given. That covers a query naming the same person twice and a query where one or both names never appear in the family tree.

Leave a blank line between the answers for one family tree and the answers for the next.