3025. [USACO Open18 Bronze] 家谱

【题目描述】

$Farmer John$拥有一个传承数代的家族经营的农场，其中的奶牛的根源同样也可以在这个农场中追溯数代。通过检索古老的记录，$Farmer John$好奇于现在的这群奶牛互相之间是什么关系。请帮帮他！

【输入格式】

输入的第一行包含$N（1≤N≤100）$，之后是两头奶牛的名字。每头奶牛的名字都是由至多$10$个大写字母$（A…Z）$组成的字符串。$Farmer John$好奇于这行输入中这两头奶牛之间的关系。

接下来的$N$行，每行包含两头奶牛的名字$X$和$Y$，表示$X$是$Y$的母亲。

【输出格式】

输出包含一行，表示输入第一行指定的两头奶牛之间的关系（简单起见，在下面的例子中，将这两头奶牛称为$BESSIE$和$ELSIE$）。下面是可能出现的不同种类的关系：

**如果$BESSIE$和$ELSIE$的母亲是同一头奶牛，输出“$SIBLINGS$”。

$BESSIE$可能是$ELSIE$的直系后代，也就是说$ELSIE$是$BESSIE$的母亲（$mother$），外祖母（$grand-mother$），外曾外祖母（$great-grand-mother$），外曾外曾外祖母（$great-great-grand-mother$），等等。如果是这种情况，输出“$ELSIE$ $is$ $the$ $(relation)$ $of$ $BESSIE$"，其中($relation$)是适当的关系，比如“$great-great-grand-mother$”。

**如果$ELSIE$不是$BESSIE$的某个祖先或姐妹，但是是$BESSIE$的某个祖先的孩子，那么$ELSIE$就是$BESSIE$的姨母（$aunt$）。（译者注：英语原题在这里表述有误，供题人已作出声明。）如果$ELSIE$是$BESSIE$的外祖母的孩子，输出“$ELSIE$ $is$ $the$ $aunt$ $of$ $BESSIE$”；如果$ELSIE$是$BESSIE$的外曾外祖母的孩子，输出“$ELSIE$ $is$ $the$ $great-aunt$ $of$ $BESSIE$”；如果$ELSIE$是$BESSIE$的外曾外曾外祖母的孩子，输出“$ELSIE$ $is$ $the$ $great-great-aunt$ $of$ $BESSIE$”；以此类推。

**如果$BESSIE$和$ELSIE$有任何其他的亲戚关系（也就是说，她们有共同的祖先），她们就是表姐妹，输出“$COUSINS$”。

**如果$BESSIE$和$ELSIE$既没有共同的祖先，其中任何一头也不是另一头的直系后代，输出“$NOT$ $RELATED$”。

下图描述了上述关系，你只需考虑这些关系。观察到有一些像是“甥女（$niece$）”（姊妹的女儿）的关系是不必要的，这是由于如果$BESSIE$是$ELSIE$的甥女，那么$ELSIE$就是$BESSIE$的姨母。

【样例输入】

7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER

【样例输出】

BB is the great-aunt of AA

【来源】

USACO 2018 OPEN CONTEST BRONZE Problem 3 Family Tree

供题：Brian Dean