染色法
曾祖父是爷爷的爸爸

#include<bits/stdc++.h>
using namespace std;
//根据name确定的人
//注意个写法确定父亲的方式是看父亲出现了没，没出现就先给父亲赋个编号
const int N = 1e5+3;
int n;
unordered_map<string,int> NA;
int fa[N],sex[N];    //sex如果为0说明该人并未存在，如果为1说明该人为男，2为女
int st[N];
bool check(int x,int y){
    //五代以内无公共祖先说的是如果找到公共祖先，对于x和y都得大于等于5(自身属于1)
    memset(st,0,sizeof st);
    // for(int i=1,j=fa[y];j!=0;)这个写法是错误的，因为做LCA的时候必须也得给自己标记了，自己也可能是公共祖先
    for(int p1=x,i=1;p1;p1=fa[p1],i++){
        st[p1]=i;
    }

    for(int p1=y,i=1;p1;p1=fa[p1],i++){
        if(st[p1]){//存在公共祖先
            if(st[p1]>4&&i>4)
                return true;
            else
                return false;
        }
    }
    return true;    //不存在公共祖先
}
int main(){
    scanf("%d",&n);
    int idx=0;
    for(int i=1;i<=n;i++){
        string n,s;
        cin>>n>>s;
        if(!NA[n])NA[n]=++idx;
        int t=NA[n];
        if(s.back()=='m')    sex[t]=1;
        else if(s.back()=='f')sex[t]=2;
        else if(s.back()=='r'){
            sex[t]=2;
            string fa_name=s.substr(0,s.size()-7);
            if(!NA[fa_name])NA[fa_name]=++idx;
            fa[t]=NA[fa_name];
        }else if(s.back()=='n'){
            sex[t]=1;
            string fa_name=s.substr(0,s.size()-4);
            if(!NA[fa_name])NA[fa_name]=++idx;
            fa[t]=NA[fa_name];
        }
    }
    int m;
    scanf("%d",&m);
    while(m--){
        string n1,s1,n2,s2;
        cin>>n1>>s1>>n2>>s2;
        int id1=NA[n1],id2=NA[n2];
        if(sex[id1]==0||sex[id2]==0)
            puts("NA");
        else{
            if(sex[id1]==sex[id2])
                puts("Whatever");
            else{
                if(check(id1,id2))
                    puts("Yes");
                else
                    puts("No");
            }
        }
    }
    return 0;
}