L2-030 冰島人 (25分)

2018年世界盃，冰島隊因1:1平了強大的阿根廷隊而一戰成名。好事者發現冰島人的名字後面似乎都有個「松」（son），於是有網友科普如下：
冰島人沿用的是維京人古老的父系姓制，孩子的姓等於父親的名加後綴，如果是兒子就加 sson，女兒則加 sdottir。因爲冰島人口較少，爲避免近親繁衍，本地人交往前先用個 App 查一下兩人祖宗若幹代有無聯繫。本題就請你實現這個 App 的功能。

輸入格式：
輸入首先在第一行給出一個正整數 N（1<N≤10
​5
​​ ），爲當地人口數。隨後 N 行，每行給出一個人名，格式爲：名 姓（帶性別後綴），兩個字串均由不超過 20 個小寫的英文字母組成。維京人後裔是可以通過姓的後綴判斷其性別的，其他人則是在姓的後面加 m 表示男性、f 表示女性。題目保證給出的每個維京家族的起源人都是男性。

隨後一行給出正整數 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

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 150001
char ch[3]={'-','1','\0'};
unsigned int hash(char *str)
{
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int h = 0;
 
    while (*str)
    {
        h =( h * a + (*str++))%N;
        a *= b;
    }
 
    return h;
}
int find(char s[][21],char t[21])
{
    int i,k;
    k=hash(t);
    while(strcmp(s[k],ch)!=0)
    {
        if(strcmp(t,s[k])==0)
          return k;
        k=(k+1)%N;
    }
    return -1;
}
int main()
{
    int n;
    char s[N][21],t[N][21];
    char tem1[21],tem2[21];
    char temp1[21],temp2[21];
    int t1[N],t2[N],top1,top2;
    int i,j,k1,a,b,c,d,x1,x2,h,k2,len,len1,len2;
    int m;
    scanf("%d",&n);
    for(i=0;i<N;i++)
    {
        strcpy(s[i],ch);
        strcpy(t[i],ch);
    }

    for(i=0;i<n;i++)
    {
        scanf("%s",tem1);
        scanf("%s",tem2);
        h=hash(tem1);
        while(strcmp(s[h],ch)!=0)
          h=(h+1)%N;
        strcpy(s[h],tem1);
        strcpy(t[h],tem2);
    }
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        scanf("%s",tem1);
        scanf("%s",tem2);
        scanf("%s",temp1);
        scanf("%s",temp2);
        k1=find(s,tem1);
        k2=find(s,temp1);
        if(k1==-1||k2==-1)
        {
            printf("NA\n");
        }
        else
        {
            a=strlen(t[k1]);
            b=strlen(tem2);
            c=strlen(t[k2]);
            d=strlen(temp2);
            x1=1;
            if(t[k1][a-1]=='n'||t[k1][a-1]=='m')
              x1=0;
            x2=1;
            if(t[k2][c-1]=='n'|| t[k2][c-1]=='m')
              x2=0; 
            if(x1==x2)
               printf("Whatever\n");
            else if(((t[k1][a-1]=='f') &&(t[k2][c-1]=='m'))||((t[k2][c-1]=='f') &&(t[k1][a-1]=='m')))
               printf("Yes\n");
            else{
                top1=0;
                top2=0;
                t1[top1]=k1;
                top1++;
                k1=find(s,tem2);
                while(k1!=-1)
                {
                    t1[top1]=k1;
                    top1++;
                    len1=strlen(t[k1]);
                    if(t[k1][len1-1]=='n')
                        len1=len1-4;
                    else
                         len1=len1-1;
                    for(j=0;j<len1;j++)
                         tem2[j]=t[k1][j];
                    tem2[j]='\0';
                    k1=find(s,tem2);
                }
                t2[top2]=k2;
                top2++;
                k2=find(s,temp2);
                 while(k2!=-1)
                {
                    t2[top2]=k2;
                    top2++;
                    len2=strlen(t[k2]);
                    if(t[k2][len2-1]=='n')
                        len2=len2-4;
                    else
                         len2=len2-1;
                    for(j=0;j<len2;j++)
                         temp2[j]=t[k2][j];
                    temp2[j]='\0';
                    k2=find(s,temp2);
                }
                if(t1[top1-1]!=t2[top2-1])
                {
                    printf("Yes\n");
                    continue;
                }
                while(top1!=0 && top2!=0 && t1[top1-1]==t2[top2-1])
                {
                    top1--;
                    top2--;

                }
                if(top1>=4&&top2>=4)
                  printf("Yes\n");
                else
                 printf("No\n");
            }           

        }
    }

   return 0;  
        
}