Family Tree

题目描述

农夫约翰拥有一座世代相传的家族农场，农场里有一群奶牛，它们的家族血统也同样可以在这座农场上追溯好几代。通过查阅旧记录，农夫约翰想知道他当前牛群中的奶牛彼此之间是如何相互关联的。请帮助他完成这项工作！

输入格式

输入的第一行包含 $N$（$1 \leq N \leq 100$），随后是两头奶牛的名字。 奶牛名字均为长度不超过 10 的大写字母字符串（$A \ldots Z$）。农夫约翰想知道这一行中两头奶牛之间的关系。 接下来的 $N$ 行每行包含两个奶牛名字 $X$ 和 $Y$，表示 $X$ 是 $Y$ 的母亲。

输出格式

你应输出一行，表示输入第一行中指定的两头奶牛之间的关系（为简化起见，下面的示例将这两头牛称为 BESSIE 和 ELSIE）。可能出现的关系类型如下： 如果 BESSIE 和 ELSIE 有相同的母亲，输出 "SIBLINGS"。 BESSIE 可能是 ELSIE 的直接后代，这意味着 ELSIE 是 BESSIE 的母亲、外祖母/祖母、曾外祖母/曾祖母、曾曾外祖母/曾曾祖母，等等。如果是这种情况，输出 "ELSIE is the (relation) of BESSIE"，其中 (relation) 为相应的关系，例如 "great-great-grand-mother"。 如果 ELSIE 是 BESSIE 某位祖先的孩子（并且 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"。

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

BB is the great-aunt of AA

提示

下图有助于说明上述关系，这些是你需要考虑的唯一关系类型。注意，一些关系如 "niece"（姐妹的女儿）并不需要，因为如果 BESSIE 是 ELSIE 的 niece，那么 ELSIE 就是 BESSIE 的 aunt。 题目作者：Brian Dean

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze