#include #include #include using namespace std; class UnionFind{ public: int parent[100001]; int rank[100001]; int n; UnionFind (int n){ this->n = n; } void reset(vector& nodes){ for (const auto& i : nodes){ parent[i] = i; rank[i] = 0; } } void reset(){ for (int i = 0; i < n; i++){ parent[i] = i; rank[i] = 0; } } int findSet (int i){ if (i != parent[i]){ parent[i] = findSet(parent[i]); } return parent[i]; } bool isSameSet(int i, int j){ return findSet(i) == findSet(j); } void uni(int i, int j){ if (!isSameSet(i, j)){ int x = findSet(i); int y = findSet(j); if (rank[x] > rank[y]){ parent[y] = x; } else { parent[x] = y; if (rank[x] == rank[y]){ rank[y]++; } } } } }; int main(){ int n, m, q, x, y, k; cin >> n >> m >> q; set> s; vector adj[n]; for (int i = 0; i < m; i++){ cin >> x >> y; x--; y--; adj[x].push_back(y); adj[y].push_back(x); s.insert(make_pair(x, y)); s.insert(make_pair(y, x)); } UnionFind UF(n); for (int qq = 0; qq < q; qq++){ cin >> k; vector nodes; set nodes_set; for (int i = 0; i < k; i++){ cin >> x; x--; nodes.push_back(x); nodes_set.insert(x); } if (k >= 300) { UF.reset(); for (const auto& l : s){ if (nodes_set.find(l.first) != nodes_set.end() && nodes_set.find(l.second) != nodes_set.end()) UF.uni(l.first, l.second); } set pars; for (const auto& i : nodes){ pars.insert(UF.findSet(i)); } cout << pars.size() << endl; } else { UF.reset(nodes); for (const auto& i: nodes){ for (const auto& j: nodes){ if (s.find(make_pair(i, j)) != s.end()){ UF.uni(i, j); } } } set pars; for (const auto& i : nodes){ pars.insert(UF.findSet(i)); } cout << pars.size() << endl; } } }