#ifdef ssu1 #define _GLIBCXX_DEBUG #endif #undef NDEBUG #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define fore(i, l, r) for(int i = (l); i < (r); ++i) #define forn(i, n) fore(i, 0, n) #define fori(i, l, r) fore(i, l, (r) + 1) #define sz(v) int((v).size()) #define all(v) (v).begin(), (v).end() #define pb push_back #define mp make_pair #define X first #define Y second #if ( _WIN32 || __WIN32__ ) #define LLD "%I64d" #else #define LLD "%lld" #endif typedef long long li; typedef long double ld; typedef pair pt; template T abs(T a) { return a < 0 ? -a : a; } template T sqr(T a) { return a*a; } const int INF = (int)1e9; const ld EPS = 1e-9; const ld PI = 3.1415926535897932384626433832795; /* This is just to check correctness of input */ void ensure(bool value){ if(!value){ fprintf(stderr, "Assertion failed"); throw; } } void ensure(bool value, string message){ if(!value){ fprintf(stderr, "Assertion failed. Message = %s", message.c_str()); throw; } } int readInt(int l, int r){ int x; if(scanf("%d", &x) != 1){ fprintf(stderr, "Expected int in range [%d, %d], but haven't found!", l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected int in range [%d, %d], but found %d!", l, r, x); throw; } return x; } int readInt(int l, int r, string name){ int x; if(scanf("%d", &x) != 1){ fprintf(stderr, "Expected int %s in range [%d, %d], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected int %s in range [%d, %d], but found %d!", name.c_str(), l, r, x); throw; } return x; } li readLong(li l, li r){ li x; if(scanf(LLD, &x) != 1){ fprintf(stderr, "Expected long long in range ["LLD", "LLD"], but haven't found!", l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected long long in range ["LLD", "LLD"], but found "LLD"!", l, r, x); throw; } return x; } li readLong(li l, li r, string name){ li x; if(scanf(LLD, &x) != 1){ fprintf(stderr, "Expected long long %s in range ["LLD", "LLD"], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected long long %s in range ["LLD", "LLD"], but found "LLD"!", name.c_str(), l, r, x); throw; } return x; } const ld __EPS__ = 1e-15; ld readDouble(double l, double r){ double x; if(scanf("%lf", &x) != 1){ fprintf(stderr, "Expected double in range [%lf, %lf], but haven't found!", l, r); throw; } if(!(l <= x + __EPS__ && x <= r + __EPS__)){ fprintf(stderr, "Expected double in range [%lf, %lf], but found %lf!", l, r, x); throw; } return x; } ld readDouble(double l, double r, string name){ double x; if(scanf("%lf", &x) != 1){ fprintf(stderr, "Expected double %s in range [%lf, %lf], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x + __EPS__ && x <= r + __EPS__)){ fprintf(stderr, "Expected double %s in range [%lf, %lf], but found %lf!", name.c_str(), l, r, x); throw; } return x; } const int __MAXBUF__ = (int)1e7; char __buf__[__MAXBUF__]; string readString(char lfc, char rgc, int lfn, int rgn){ ensure(scanf(" %s ", __buf__) == 1, "Expected string, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String have incorrect length"); forn(i, sz(ans)) ensure(lfc <= ans[i] && ans[i] <= rgc, "String contains incorrect characters"); return ans; } string readString(string pat, int lfn, int rgn){ ensure(scanf(" %s ", __buf__) == 1, "Expected string, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String have incorrect length"); forn(i, sz(ans)) ensure(find(all(pat), ans[i]) != pat.end(), "String contains incorrect characters"); return ans; } string readString(char lfc, char rgc, int lfn, int rgn, string name){ ensure(scanf(" %s ", __buf__) == 1, "Expected string " + name + ", haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String " + name + " have incorrect length"); forn(i, sz(ans)) ensure(lfc <= ans[i] && ans[i] <= rgc, "String " + name + " contains incorrect characters"); return ans; } string readString(string pat, int lfn, int rgn, string name){ ensure(scanf(" %s ", __buf__) == 1, "Expected string " + name + ", haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String " + name + " have incorrect length"); forn(i, sz(ans)) ensure(find(all(pat), ans[i]) != pat.end(), "String " + name + " contains incorrect characters"); return ans; } string readLine(char lfc, char rgc, int lfn, int rgn){ ensure(gets(__buf__) != NULL, "Line expected, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "Line have incorrect length"); forn(i, sz(ans)) ensure(lfc <= ans[i] && ans[i] <= rgc, "Line contains incorrect characters"); return ans; } string readLine(string pat, int lfn, int rgn){ ensure(gets(__buf__) != NULL, "Line expected, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "Line have incorrect length"); forn(i, sz(ans)) ensure(find(all(pat), ans[i]) != pat.end(), "Line contains incorrect characters"); return ans; } string readLine(){ ensure(gets(__buf__) != NULL, "Line expected, haven't found"); string ans = __buf__; return ans; } char readChar(){ char c; ensure(scanf(" %c ", &c) == 1, "Non-whitespace character expected"); return c; } char readWChar(){ int ans = getchar(); ensure(ans != EOF, "Character expected"); return (char)ans; } const int NMAX = 300; int n, r; map idx; vector nms; int getIdx(string s){ if(idx.count(s) == 0){ int id = sz(idx); nms.pb(s); idx[s] = id; } return idx[s]; } int tree[NMAX], bs[NMAX], gender[NMAX]; vector par[NMAX]; void init(int c[NMAX]){ forn(i, NMAX) c[i] = i; } int root(int c[NMAX], int v){ return c[v] == v ? v : c[v] = root(c, c[v]); } int merge(int c[NMAX], int v, int u){ v = root(c, v); u = root(c, u); if(v == u) return 0; c[v] = u; return 1; } void set_gender(int id, int g){ if(g == -1) return; if(gender[id] == -1){ gender[id] = g; }else assert(gender[id] == g); } void set_parent(int id, int p){ if(p == -1) return; assert(find(all(par[id]), p) == par[id].end()); par[id].pb(p); assert(sz(par[id]) <= 2); } int dst[NMAX][NMAX]; int main(){ #ifdef ssu1 assert(freopen("input.txt", "rt", stdin)); //assert(freopen("output.txt", "wt", stdout)); #endif n = readInt(2, 256); r = readInt(1, n - 1); memset(gender, -1, sizeof gender); init(tree); init(bs); { set first_part; forn(i, r){ string n1 = readString('a', 'z', 1, 4); string is = readString('a', 'z', 1, 100); string f = readString('a', 'z', 1, 100); string of = readString('a', 'z', 1, 100); string n2 = readString('a', 'z', 1, 4); assert(is == "is"); assert(of == "of"); assert(f == "father" || f == "mother" || f == "sister" || f == "brother" || f == "son" || f == "daughter"); assert(first_part.count(n1) == 0); first_part.insert(n1); int id1 = getIdx(n1); int id2 = getIdx(n2); assert(merge(tree, id1, id2)); assert(n1 != n2); if(f == "father"){ set_gender(id1, 1); set_parent(id2, id1); } if(f == "mother"){ set_gender(id1, 0); set_parent(id2, id1); } if(f == "brother"){ set_gender(id1, 1); merge(bs, id1, id2); } if(f == "sister"){ set_gender(id1, 0); merge(bs, id1, id2); } if(f == "son"){ set_gender(id1, 1); set_parent(id1, id2); } if(f == "daughter"){ set_gender(id1, 0); set_parent(id1, id2); } } assert(sz(idx) == n); forn(i, n){ forn(j, n){ bool have = false; forn(ii, sz(par[i])) forn(jj, sz(par[j])){ if(par[i][ii] == par[j][jj]) have = true; } if(have) merge(bs, i, j); } } forn(i, n){ if(i == root(bs, i)){ vector ps = par[i]; forn(j, n){ if(root(bs, i) == root(bs, j) && i != j){ ps.insert(ps.end(), all(par[j])); } } sort(all(ps)); ps.erase(unique(all(ps)), ps.end()); if(sz(ps) > 2){ printf("person %s have %d parents:\n", nms[i].c_str(), sz(ps)); forn(j, sz(ps)){ printf("%s\n", nms[ps[j]].c_str()); } throw; } if(sz(ps) == 2){ int p1 = ps[0]; int p2 = ps[1]; if(gender[p1] != -1 && gender[p2] != -1 && gender[p1] == gender[p2]){ cerr << "equal genders!" << endl; throw; } } forn(j, n){ if(root(bs, j) == root(bs, i)) par[j] = ps; } forn(j, sz(ps)){ assert(root(bs, ps[j]) != root(bs, i)); } } } } memset(dst, 63, sizeof dst); forn(i, n){ dst[i][i] = 0; forn(j, n){ if(i == j) continue; if(root(bs, i) == root(bs, j)) dst[i][j] = 1; else{ if(find(all(par[i]), j) != par[i].end() || find(all(par[j]), i) != par[j].end()) dst[i][j] = 1; } } } forn(t, n){ forn(i, n) forn(j, n) dst[i][j] = min(dst[i][j], dst[i][t] + dst[t][j]); } int q = readInt(1, 16384); forn(qi, q){ string x = readString('a', 'z', 1, 4); string y = readString('a', 'z', 1, 4); assert(idx.count(x) && idx.count(y)); assert(x != y); int ix = getIdx(x); int iy = getIdx(y); printf("%d\n", (dst[ix][iy] < INF ? dst[ix][iy] : -1)); } return 0; }