L2-030 冰岛人 （25 分)_2018年世界杯,冰岛队因1：1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字-CSDN博客

　　L2-030 冰岛人 （25 分)

　　2018年世界杯，冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”（son），于是有网友科普如下：

　　冰岛人沿用的是维京人古老的父系姓制，孩子的姓等于父亲的名加后缀，如果是儿子就加 sson，女儿则加 sdottir。因为冰岛人口较少，为避免近亲繁衍，本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。 输入格式：

　　输入首先在第一行给出一个正整数 N（1

　　随后一行给出正整数 M，为查询数量。随后 M 行，每行给出一对人名，格式为：名1 姓1 名2 姓2。注意：这里的姓是不带后缀的。四个字符串均由不超过 20 个小写的英文字母组成。

　　题目保证不存在两个人是同名的。 输出格式：

　　对每一个查询，根据结果在一行内显示以下信息：

　　若两人为异性，且五代以内无公共祖先，则输出 Yes；

　　若两人为异性，但五代以内（不包括第五代）有公共祖先，则输出 No；

　　若两人为同性，则输出 Whatever；

　　若有一人不在名单内，则输出 NA。

　　所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。 输入样例：

　　15

　　chris smithm

　　adam smithm

　　bob adamsson

　　jack chrissson

　　bill chrissson

　　mike jacksson

　　steve billsson

　　tim mikesson

　　april mikesdottir

　　eric stevesson

　　tracy timsdottir

　　james ericsson

　　patrick jacksson

　　robin patricksson

　　will robinsson

　　6

　　tracy tim james eric

　　will robin tracy tim

　　april mike steve bill

　　bob adam eric steve

　　tracy tim tracy tim

　　x man april mikes 输出样例：

　　Yes

　　No

　　No

　　Whatever

　　Whatever

　　NA 题解

　　样例图解

　　第一次查 10、11号节点，最近公共父节点为0号节点，0到10和11的距离均为4，成立，输出Yes；

　　第二次查 14、10号节点，最近公共父节点为3号节点，3到10和11的距离均为3，不成立，输出No；

　　第三次查8，6号节点，最近公共父节点为0号节点，0到8的距离均为3，0到和6的距离为2，不成立，输出No；

　　第四五次查询性别相同，输出Whatever

　　第六次查询，信息不存在，输出NA。

　　记下每一个人的父节点，然后找最近公共父节点，再检查最近公共父节点到两个人之间的距离是否都大于3（所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。）。 代码