Climbing Trees

表达式树、B/B*树、红黑树、四叉树、PQ树……，树在计算机科学的许多领域中都扮演了重要的角色。有些问题的名称表明其使用了树结构，比如智能规划问题在传统上称作“猴子与香蕉”问题。有些问题确实用到了树的结构，但在它的名称中并没有表示出来，比如哈夫曼编码。 本问题是要确定两个人是否在一个家谱中存在亲属关系。 给定一系列的“子-父”姓名对作为家谱，每对姓名中前者为子，后者为父（单亲）。再给定一系列的待查姓名对，表示两个人的姓名。你要写一个程序来确定待查 对中的两个姓名是否在家谱中是否存在亲属关系。如果确定待查对中的两个姓名存在亲属关系，则需输出是何种关系。大学里学生和导师的关系就可以视为单亲血统的例子（我们假设每个学生只有一个导师，没有共同指导的情况）。 在这个问题中，“子-父”对p q表示p是q的子。在确定姓名关系的过程中，我们有以下的归纳定义： p是q的第0个后代，当且仅当输入序列中存在一个“子-父”对p q，指出了p和q为“子-父”关系 p是q的第k个后代，当且仅当r是q的(k - 1)个后代，并且输入序列中存在一个“子-父”对p r，指出了p和r为“子-父”关系。 就此问题而言，p和q两人之间的亲属关系只能是以下4种关系中的一种： 1子关系——包括孙“grand child”、曾孙“great grand child”、玄孙“great great grand child”等。 根据定义，p是q的“child”（子），当且仅当输入序列中存在一个“子-父”对p q，指出了它们为“子-父”关系（即p是q的第0个后代）；p是q的“grand child”（孙）当且仅当p是q的第1个后代；且：当且仅当p是q的第(n + 1)个后代。  2父关系——包括祖父“grand parent”、曾祖父“great grand parent”、高祖父“great great grand parent”等。 父关系的定义与子关系对应，参见上面的“子关系”。 3堂亲——第0堂亲“0th cousin”、第1堂亲“1st cousin”、第2堂亲等“2nd cousin”。堂亲存在隔代关系，隔1代、隔2代、隔3代等。 （译注：美国的堂亲关系与中国的相差很大，“nth cousin”中的n是指二人中辈份较长的一人与最近共同祖先相差的辈数减1。比如你和姑妈（父亲的亲姐妹）的最近 共同祖先是祖父，关系就是0th cousin；你和堂弟（姑妈的儿子）的最近共同祖先也是祖父，关系则是1st cousin；你和姨奶（奶奶的亲姐妹）儿子的关系是2nd cousin。两个cousin关系的人相差的辈数m，用“cousin removed m”来表示。） 4同胞——“0th cousins removed 0 times”为同胞“siblings”（他们有共同的父）。  # The Input ## 输入 输入由一系列的名字对构成，每对独占一行。各对中的名字都由小写字母和点号（比如可用来分隔姓和名）构成。子和父之间由1个或多个空格隔开。当输入的姓名对前者的名字为“no.child”时，表示“子-父”对输入结束。结束符仅仅用于分隔“子-父”对和待查对，程序不能将其作为一个“子-父”对来处理。输入中不会存在循环关系，即任何名字p都不可能同为q的后代和祖先。 “子-父”对下面是待查对，格式与“子-父”对相同，即每个待查对中的名字都由小写字母和点号构成，两个名字间由1个或多个空格隔开。待查对的输入由EOF结束。 总共最多出现300个不同的名字（包括“子-父”对和待查对）。所有姓名都少于31个字符长度。最多100个待查对。 # The Output ## 输出 对于每个姓名待查对，都要以下列的输出形式表示p与q的关系 child, grand child, great grand child, great great ...great grand child parent, grand parent, great grand parent, great great ...great grand parent sibling n cousin removed m no relation 如果一个“m cousin”相隔0代，那么只需打印出“m cousin”，也就是说输出中不能出现“removed 0”。不要在任何数字后面添加“st”、“nd”、“rd”、“th”等后缀。 # Sample Input ## 输入示例 ``` alonzo.church oswald.veblen stephen.kleene alonzo.church dana.scott alonzo.church martin.davis alonzo.church pat.fischer hartley.rogers mike.paterson david.park dennis.ritchie pat.fischer hartley.rogers alonzo.church les.valiant mike.paterson bob.constable stephen.kleene david.park hartley.rogers no.child no.parent stephen.kleene bob.constable hartley.rogers stephen.kleene les.valiant alonzo.church les.valiant dennis.ritchie dennis.ritchie les.valiant pat.fischer michael.rabin ``` # Sample Output ## 输出示例 ``` parent sibling great great grand child 1 cousin removed 1 1 cousin removed 1 no relation ```

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=51 [PDF](https://uva.onlinejudge.org/external/1/p115.pdf) 



alonzo.church oswald.veblen
stephen.kleene alonzo.church
dana.scott alonzo.church
martin.davis alonzo.church
pat.fischer hartley.rogers
mike.paterson david.park
dennis.ritchie pat.fischer
hartley.rogers alonzo.church
les.valiant mike.paterson
bob.constable stephen.kleene
david.park hartley.rogers
no.child no.parent
stephen.kleene bob.constable
hartley.rogers stephen.kleene
les.valiant alonzo.church
les.valiant dennis.ritchie
dennis.ritchie les.valiant
pat.fischer michael.rabin

parent
sibling
great great grand child
1 cousin removed 1
1 cousin removed 1
no relation