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

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

输入格式：

输入首先在第一行给出一个正整数 N（1<N≤105），为当地人口数。随后 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

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

Java实现：

/**
 * 思路：
 * 1. 家谱建模：用 father[] 数组建立“儿子/女儿 -> 父亲”的单向链接。
 * 2. 维京逻辑：解析姓氏后缀推导出父亲名。特别注意：推导出的父亲即便不在名单开头，其性别也定为男。
 * 3. NA 判定：只有在输入 N 个人名时作为“名”正式出现过的人，才算在名单内。
 * 4. 亲缘算法：
 * - 从 A 向上追溯所有祖先并记录“代数”深度（自己是1代）。
 * - 从 B 向上追溯，遇到 A 的祖先时，检查双方深度。
 * - 只要任一方深度 < 5，即表示“五代以内有公共祖先”。
 * 5. 性能优化：
 * - 用 HashMap 转换 String 为 int ID，之后操作全是数组，规避 Java 频繁 GC。
 * - 核心技巧：用 visitedTag[] 配合当前查询编号，实现 $O(1)$ 的状态重置。
 */

import java.util.*;
import java.io.*;

public class Main {
    static int[] father = new int[200005]; 
    static int[] gender = new int[200005]; // 1:男, 0:女
    static boolean[] isExist = new boolean[200005]; // 标记是否在正式名单中
    static Map<String, Integer> nameToId = new HashMap<>(100005);
    static int idCount = 1;

    // 路径标记系统：通过 tag 区分当前是第几次查询，省去清空数组的时间
    static int[] visitedTag = new int[200005]; 
    static int[] depthA = new int[200005];

    static int getId(String s) {
        Integer id = nameToId.get(s);
        if (id == null) {
            id = idCount++;
            nameToId.put(s, id);
            father[id] = -1;
            gender[id] = -1;
            return id;
        }
        return id;
    }

    public static void main(String[] args) throws Exception {
        Reader sc = new Reader(System.in);
        int n = sc.nextInt();
        
        Arrays.fill(father, -1);
        Arrays.fill(gender, -1);

        for (int i = 0; i < n; i++) {
            String fName = sc.next();
            String lName = sc.next();
            int id = getId(fName);
            isExist[id] = true; 
            
            // 处理后缀：截取长度要准
            if (lName.endsWith("m")) {
                gender[id] = 1;
            } else if (lName.endsWith("f")) {
                gender[id] = 0;
            } else if (lName.endsWith("sson")) {
                gender[id] = 1;
                int fid = getId(lName.substring(0, lName.length() - 4));
                father[id] = fid;
                gender[fid] = 1; // 关键：父亲必须标记为男性，否则查无此人性别
            } else if (lName.endsWith("sdottir")) {
                gender[id] = 0;
                int fid = getId(lName.substring(0, lName.length() - 7));
                father[id] = fid;
                gender[fid] = 1; 
            }
        }

        int m = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int q = 1; q <= m; q++) {
            String n1 = sc.next(); sc.next();
            String n2 = sc.next(); sc.next();

            Integer id1 = nameToId.get(n1);
            Integer id2 = nameToId.get(n2);

            // 先判 NA，再判同性，最后搜家谱
            if (id1 == null || id2 == null || !isExist[id1] || !isExist[id2]) {
                sb.append("NA\n");
            } else if (gender[id1] == gender[id2]) {
                sb.append("Whatever\n");
            } else {
                if (check(id1, id2, q)) sb.append("Yes\n");
                else sb.append("No\n");
            }
        }
        System.out.print(sb);
    }

    static boolean check(int a, int b, int tag) {
        int curr = a;
        int d = 1;
        // 标记 A 这一脉所有祖先及其深度
        while (curr != -1) {
            visitedTag[curr] = tag; 
            depthA[curr] = d;
            curr = father[curr];
            d++;
        }

        curr = b;
        int d2 = 1;
        // B 向上爬，撞到标记说明有公共祖先
        while (curr != -1) {
            if (visitedTag[curr] == tag) {
                int d1 = depthA[curr];
                // 如果相遇点在双方任一方的5代内（d < 5），则不符合
                if (d1 < 5 || d2 < 5) return false;
                else return true; 
            }
            curr = father[curr];
            d2++;
        }
        return true;
    }

    static class Reader {
        private InputStream in;
        private byte[] buf = new byte[1024 * 64];
        private int ptr = 0, len = 0;
        public Reader(InputStream in) { this.in = in; }
        private int read() throws Exception {
            if (ptr < len) return buf[ptr++];
            len = in.read(buf); ptr = 0;
            return len == -1 ? -1 : buf[ptr++];
        }
        public String next() throws Exception {
            int c = read();
            while (c >= 0 && c <= 32) c = read();
            if (c == -1) return null;
            StringBuilder sb = new StringBuilder();
            while (c > 32) { sb.append((char) c); c = read(); }
            return sb.toString();
        }
        public int nextInt() throws Exception {
            int c = read();
            while (c >= 0 && c <= 32) c = read();
            int res = 0;
            while (c >= '0' && c <= '9') { res = res * 10 + (c - '0'); c = read(); }
            return res;
        }
    }
}