#P10124. [USACO18OPEN] Family Tree B

[USACO18OPEN] Family Tree B

题目描述

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

输入格式

输入的第一行包含 NN1N1001\le N\le 100),之后是两头奶牛的名字。每头奶牛的名字都是由至多 1010 个大写字母(A-Z)组成的字符串。Farmer John 好奇于这行输入中这两头奶牛之间的关系。

接下来的 NN 行,每行包含两头奶牛的名字 XXYY,表示 XXYY 的母亲。

输出格式

输出包含一行,表示输入第一行指定的两头奶牛之间的关系(简单起见,在下面的例子中,将这两头奶牛称为 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