#include #include #include #include using namespace std; vector> graph; vector> proposals; vector pro; class UnionFind { private: vector p, rank; public: int sets; UnionFind(int N) { rank.assign(N, 0); p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; sets = N; } int findSet(int i) { if (p[i] == i) { return i; } int tmp = findSet(p[i]); p[i] = tmp; return p[i]; } bool isSameSet(int i, int j) { return findSet(i) == findSet(j); } void unionSet(int i, int j) { if (!isSameSet(i, j)) { sets--; int x = findSet(i), y = findSet(j); if (rank[x] > rank[y]) { p[y] = x; } else { p[x] = y; if (rank[x] == rank[y]) { rank[y]++; } } } } }; int main() { int V, E, P, a, b, p, id; string line; cin >> V >> E >> P; for (int i = 0; i < V; i++) { graph.emplace_back(); } for (int i = 0; i < E; i++) { cin >> a >> b; a--; b--; graph[a].emplace_back(b); graph[b].emplace_back(a); } cin.ignore(); for (int i = 0; i < P; i++) { stringstream ss; getline(cin, line); ss << line; pro.clear(); proposals.clear(); for (int j = 0; j < V; j++) { proposals.emplace_back(); } while (ss >> p) { p--; pro.emplace_back(p); } UnionFind uf(pro.size()); id = 0; for (const auto &p : pro) { if (!proposals[p].empty()) { uf.unionSet(id, proposals[p].back()); } else { for (int j = 0; j < graph[p].size(); j++) { if (!proposals[graph[p][j]].empty()) { uf.unionSet(id, proposals[graph[p][j]].back()); } } } proposals[p].emplace_back(id); id++; } cout << uf.sets << endl; } return 0; }