问题6694--家谱

6694: 家谱

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

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

输入格式(文件名:family.in):

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

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

输出格式(文件名:family.out):

输出包含一行,表示输入第一行指定的两头奶牛之间的关系(简单起见,在下面的例子中,将这两头奶牛称为BESSIEELSIE)。下面是可能出现的不同种类的关系:

如果BESSIEELSIE的母亲是同一头奶牛,输出“SIBLINGS”

l BESSIE可能是ELSIE的直系后代,也就是说ELSIEBESSIE的母亲(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)。(译者注:英语原题在这里表述有误,供题人已作出声明。)如果ELSIEBESSIE的外祖母的孩子,输出“ELSIE is the aunt of BESSIE”;如果ELSIEBESSIE的外曾外祖母的孩子,输出“ELSIE is the great-aunt of BESSIE”;如果ELSIEBESSIE的外曾外曾外祖母的孩子,输出“ELSIE is the great-great-aunt of BESSIE”;以此类推。

如果BESSIEELSIE有任何其他的亲戚关系(也就是说,她们有共同的祖先),她们就是表姐妹,输出“COUSINS”

如果BESSIEELSIE既没有共同的祖先,其中任何一头也不是另一头的直系后代,输出“NOT RELATED”

下图描述了上述关系,你只需考虑这些关系。观察到有一些像是甥女(niece(姊妹的女儿)的关系是不必要的,这是由于如果BESSIEELSIE的甥女,那么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-公开赛-铜-3

来源/分类