//Distant relatives - DIREL #include #include #include #include #include #include #include using namespace std; enum Relation { parent, child, sibling, none }; Relation inv_rel[] = {child, parent, sibling}; Relation equation(Relation r1, Relation r2) { switch (r1){ case parent: if (r2 == sibling){ return parent; } break; case child: if (r2 == parent){ return sibling; } break; case sibling: switch (r2){ case sibling: return sibling; case child: return child; default: return none; } } return none; } // We will use adjacency list representation struct Edge { Relation r; int v; Edge(){} Edge(Relation _r, int _v) : r(_r), v(_v){} }; class DIREL { int num_of_people; unordered_map rmap; unordered_map nmap; vector names; vector> graph; int addPerson(const string &name, int &index); void inverseRelations(int skip); void closure(); public: DIREL(int n) : num_of_people(n), graph(n) { rmap["father"] = parent; rmap["mother"] = parent; rmap["son"] = child; rmap["daughter"] = child; rmap["brother"] = sibling; rmap["sister"] = sibling; names.reserve(n); } void computeRelations(int n); void queries(int q); }; int DIREL::addPerson(const string &name, int &index) { if (nmap.count(name) == 0){ nmap[name] = index; names.push_back(name); return index++; }else{ return nmap[name]; } } void DIREL::computeRelations(int n) { string a, is, rel, of, b, g; int index = 0, r; cin >> r; for (int i = 0; i < r; i++){ cin >> a >> is >> rel >> of >> b; int u = addPerson(a, index); Edge edge; edge.r = rmap[rel]; edge.v = addPerson(b, index); graph[u].push_back(edge); } inverseRelations(-1); closure(); } void DIREL::inverseRelations(int skip) { for (int i = 0; i < num_of_people; i++){ if (graph[i].size() && i != skip){ Edge &edge = graph[i].front(); graph[edge.v].push_back(Edge(inv_rel[edge.r], i)); } } } void DIREL::closure() { vector v(num_of_people); for (int i = 0; i < num_of_people; i++){ int c = 2*i + 1; //anything less than this is not visited v[i] = c; for (auto edge : graph[i]){ v[edge.v] = c+1; } for (auto it = begin(graph[i]); it != end(graph[i]); ++it){ for (auto it2 = begin(graph[it->v]); it2 != end(graph[it->v]); ++it2){ if (v[it2->v] < c){ v[it2->v] = c+1; Relation r = equation(it->r, it2->r); if (r != none){ graph[i].push_back(Edge(r, it2->v)); graph[it2->v].push_back(Edge(inv_rel[r], i)); } } } } } } void DIREL::queries(int q) { string a, b; vector vis(num_of_people), dist(num_of_people); for (int i = 1; i <= q; i++){ cin >> a >> b; queue q; int n = -1, na = nmap[a], nb = nmap[b]; q.push(na); vis[na] = i; dist[na] = 0; while (n != nb && q.size()){ n = q.front();q.pop(); for (auto edge : graph[n]){ if (vis[edge.v] < i){ dist[edge.v] = dist[n]+1; if (edge.v == nb){ n = nb; break; } vis[edge.v] = i; q.push(edge.v); } } } if (n == nb) cout << dist[n] << endl; else cout << "-1\n"; } } int main() { ios_base::sync_with_stdio(false); int n, q; cin >> n; DIREL direl(n); direl.computeRelations(n-1); cin >> q; direl.queries(q); }