#include #include #include #include #include #include int levelOf(const std::string & s){ int level = 0; for(int i = 0; i < s.size() && s[i] == ' '; i++){level++;} return level; } struct Tree; static std::map dict; struct Tree{ Tree * parent; std::list children; std::string name; Tree(const std::string & s, Tree * p){ name = s; parent = p; } Tree * lastChild() const {return children.back();} void addChild(const std::string & s){ Tree * p = new Tree(s, this); //std::cout << "dict[" << s << "] = " << p << std::endl; dict[s] = p; children.push_back(p); } }; void get(Tree * t, int n){ int level = -1; for(int i = 0; i < n; i++){ //std::cout << "i = " << i << std::endl; std::string line; std::getline(std::cin, line); int l = levelOf(line); //std::cout << "l = " << l << ", line = " << line << std::endl; while(l != level + 1){ t = t->parent; level--; } t->addChild(line.substr(l)); t = t->lastChild(); level++; } } #define ERROR() {std::cerr << "at " << __LINE__ << ": X = " << X << ", Y = " << Y << std::endl; exit(1);} //X is a child of Y bool child(const std::string &X, const std::string & Y){ Tree * x = dict[X], *y = dict[Y]; if(x == 0 || y == 0){ERROR()} for(std::list::const_iterator i = y->children.begin(); i != y->children.end(); i++){ if(*i == x){ return true; } } return false; } bool parent(const std::string &X, const std::string & Y){ return child(Y, X); } bool sibling(const std::string &X, const std::string & Y){ Tree * x = dict[X], *y = dict[Y], *parent; if(x == 0 || y == 0){ERROR()} parent = x->parent; if(parent == 0 || y->parent != parent){return false;} return true; } //X is a descendant of Y bool descendant(const std::string &X, const std::string & Y){ if(X == ""){return false;} Tree * x = dict[X], *y = dict[Y], *parent; if(x == 0 || y == 0){ERROR()} if(x == y){return true;} return descendant(x->parent->name, Y); } bool ancestor(const std::string &X, const std::string & Y){ return descendant(Y, X); } #define IF_(func, str) if(pred == str){return func(X, Y);} bool test(const std::string & X, const std::string & Y, const std::string & pred){ IF_(child, "child"); IF_(parent, "parent"); IF_(sibling, "sibling"); IF_(descendant, "descendant"); IF_(ancestor, "ancestor"); std::cerr << "error!! X = " << X << ", Y = " << Y << ", pred = " << pred << std::endl; exit(1); } int main(){ int hoge = 0; while(true){ int n, m; std::string line; std::cin >> n >> m; if(n == 0 && m == 0){break;} //if(hoge++){std::cout << std::endl;} dict.clear(); std::getline(std::cin, line); Tree root("", 0); get(&root, n); for(int i = 0; i < m; i++){ std::getline(std::cin, line); char X[100], Y[100], a[10], relation[100]; sscanf(line.c_str(), "%s is %s %s of %s", &X, &a, &relation, &Y); Y[strlen(Y) - 1] = '\0'; //std::cout << "Y = " << Y << std::endl; if(test(X, Y, relation)){ std::cout << "True" << std::endl; }else{ std::cout << "False" << std::endl; } } std::cout << std::endl; } }