For the purposes of this problem, let us define a tree to be an acyclic directed graph in which every node ---except for a distinguished node called the root--- has exactly one outgoing edge. The root has no outgoing edges. Let u and v be nodes in a tree. If there is an edge from u to v, then v is said to be the parent of u. (Equivalently, u is said to be the child of v.) More generally, u is said to be a descendant of v (equivalently, v is said to be an ancestor of u) if there is a path from u to v. In particular, because there is a (trivial) path from every node to itself, every node is considered to be an ancestor and a descendant of itself. An ancestor (respectively, descendant) of a node that is distinct from the node is referred to as a proper ancestor (respectively, descendant) of the node.
A forest is a collection of trees.
Let u and v be nodes in a forest. If u and v occur in distinct trees of the forest, we say that they are unrelated to each other. If, on the other hand, u and v occur in the same tree, there is a unique node, referred to as the lowest common ancestor of u and v, such that
Consider the forest (of two trees) illustrated below. (All edges are understood to be pointing upwards.) Using the notation LCA(u,v) to denote the lowest common ancesor of u and v, we have LCA(I,F) = B, LCA(H,L) = A, and LCA(J,B) = B. LCA(G,R), on the other hand, is undefined, because G and R occur in separate trees of the forest.
A Q
/ | \ |
/ | \ |
/ | \ |
B C D R
/ | | | / \
/ | | | / \
E F G H S T
/ | | / \
/ | | / \
I J K L M
/|\
/ | \
N O P
Let m and n be the distances from u to LCA(u,v) and from v to LCA(u,v), respectively, and let p = min(m,n) and q = |m - n|. Then we say that u and v are (p-1)-st cousins q times removed. In the case that p=0, we have that either u or v is an ancestor of the other. Rather than referring to them as (-1)-th cousins, we usually say that v is the q-th generation ancestor of u (equivalently, that u is the q-th generation descendant of v), or the other way around, whichever is appropriate.
Develop a program that, given as input a forest of trees, followed by a sequence of pairs of nodes, reports for each such pair of nodes the relationship that the two have to one another. You are to assume that there are 26 nodes in the forest, the names of which are the upper case letters A through Z.
The first line of input will contain a single natural number N indicating the number of edges in the forest. On each of the next N lines will be a pair of upper case letters indicating the existence of an edge from the node named by the first letter to the node named by the second. Following that will be more lines of input, each containing a pair of upper case letters. For each of these pairs, your program should produce as output a message that reports the relationship between the two nodes named. There are four classes of possible relationships: none, ancestor, descendant, or cousin. See the sample output for the correct kind of message to provide in each of the four cases. (A node's relationship to itself is 0-th generation descendant (or ancestor).)
Sample Input
18 DA EB NJ OJ PJ CA HD IE MG JE KF LG FB BA GC RQ SR TR IF HL JB BJ RR GR
Sample Output
IF: 0-th cousins 1 times removed HL: 1-th cousins 1 times removed JB: 2-th generation descendant BJ: 2-th generation ancestor RR: 0-th generation descendant GR: no relation