Anthropological research is very interested in families, so researchers collected some family genealogies for research. In the experiment, the family tree is processed by computer. To achieve this, the researchers converted the genealogy into a text file. The following is an example of a genealogy text file:

John
  Robert
    Frank
    Andrew
  Nancy
    David

In the genealogy text file, each line contains a person's name. The name in the first line is the earliest ancestor of the family. The genealogy contains only the descendants of the earliest ancestors, and their husbands or wives do not appear in the genealogy. Each child indents two more spaces than their parents. Taking the above genealogy text file as an example, John, the earliest ancestor of the family, has two children Robert and Nancy, Robert has two children Frank and Andrew, and Nancy has only one child David.

In the experiment, the researchers also collected family documents and extracted statements about the relationship between two people from the family tree. The following is an example of the statement statement of the relationship in the Genealogy:

John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert

Researchers need to judge whether each statement is true or false. Please write a program to help researchers judge.

Input format:

Input first gives two positive integers N (2 ≤ N ≤ 100) and m (≤ 100), where N is the number of names in the genealogy and M is the number of statements in the genealogy. Each line of input shall not exceed 70 characters.

The name string consists of no more than 10 English letters. There is no indented space before the name given in the first line of the family tree. Other names in the genealogy shall be indented by at least 2 spaces, that is, they are the descendants of the earliest ancestor in the Genealogy (the name given in the first line). If a name in the genealogy is indented by k spaces, the name in the next line shall be indented by k+2 spaces at most.

The same name will not appear twice in a genealogy, and the name that does not appear in the genealogy will not appear in the statement. The format of each statement is as follows, where X and Y are different names in the Genealogy:

X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y

Output format:

For each statement in the test case, True is output in one line. If the statement is True, or False, if the statement is False.

Input sample:

6 5
John
  Robert
    Frank
    Andrew
  Nancy
    David
Robert is a child of John
Robert is an ancestor of Andrew
Robert is a sibling of Nancy
Nancy is the parent of Frank
John is a descendant of Andrew

Output example:

True
True
True
False
False

The first time I saw this question was in the winter vacation. At that time, I just learned trees, and I couldn't figure out the binary tree. Where would this kind of multi fork tree problem be? So during the winter vacation, I was trapped in Jianshu.

Many attempts were made to solve the problem during the winter vacation, which fail ed. (I'm too good)

After all, I still have to face this problem. Seeing this problem again is this assignment.

The following is the practice of sudden inspiration last night (the code knocked today): (achievement + consideration of situation)

#include<bits/stdc++.h>
using namespace std;
string name[110];
map<string,string>fa; //Because the number of child nodes is uncertain, there is no way to build a tree with the method of binary tree. Here, the method of map is adopted, that is, the idea of merging and searching sets
int main(){
    //freopen("alltxt.txt","r",stdin);
    int n,m;
    cin>>n>>m;
    getchar();//getline will read the carriage return. Here is a point of attention
    string s;
    
    //Build a tree
    for(int i=0;i<n;i++){
        getline(cin,s);
        int kong=count(s.begin(),s.end(),' ');
        if(kong==0){
            fa[s]="#"; //The parents of ancestors can be recorded as "#"
            name[0]=s;
        }
        else{
            s=s.erase(0,kong); //Remove spaces
            //The following two sentences of code are what I didn't think of when I did it in winter vacation - the second point that trapped me in winter vacation
            name[kong/2]=s; //It has the function of temporarily recording the parents of the previous level, and the same level is covered
            fa[s]=name[kong/2-1]; //Record parents
        }
    }
    
    //Consider by case
    string op;
    for(int i=0;i<m;i++){
        getline(cin,op);
        //Find a way to separate x and y, and then proceed to the next operation. Here, the interception of string is used 
        //This is an annoying place
        string x=op.substr(0,op.find(" is"));
        string y=op.substr(op.find("of ")+3,op.length());
        //Looking for y's child
        //This situation is in line with our achievements - to record our parents
        if(op.find("child")!=string::npos){
            if(fa[x]==y)cout<<"True"<<endl;
            else cout<<"False"<<endl;
        }
        //Find y's parents, the inverse process of the previous case
        //This situation is in line with our achievements - to record our parents
        else if(op.find("parent")!=string::npos){
            if(fa[y]==x)cout<<"True"<<endl;
            else cout<<"False"<<endl;
        }
        //Looking for y's brothers and sisters
        //Just judge whether the parents of x and y are the same. This situation is in line with our goal of building a record of parents
        else if(op.find("sibling")!=string::npos){
            if(fa[x]==fa[y])cout<<"True"<<endl;
            else cout<<"False"<<endl;
        }
        //Looking for y's descendants
        //Since our fa[y] represents Y's parents, which is not conducive to finding descendants. Considering that the two statements "Y's descendants are x" and "X's ancestors are y" are equivalent, we can consider starting with X as long as we know whether X's ancestors are y. this is consistent with the next case - finding Y's ancestors. Just change the code a little (I use this method), or merge the two cases.
        else if(op.find("descendant")!=string::npos){
            int flag=1;
            while(x!="#") {/ / keep looking until you find the head
                if(fa[x]==y){
                    cout<<"True"<<endl;
                    flag=0;
                    break;
                }
                x=fa[x];
            }
            if(flag)cout<<"False"<<endl;  //I didn't find the head
        }
        //Find y's ancestors
        //This situation is in line with our achievements - to record our parents
        else if(op.find("ancestor")!=string::npos){
            int flag=1;
            while(y!="#"){
                if(fa[y]==x){  //I've been looking for it since I didn't find the head
                    cout<<"True"<<endl;
                    flag=0;
                    break;
                }
                y=fa[y];
            }
            if(flag)cout<<"False"<<endl;  //I didn't find the head
        }
    }
    return 0;
}