#line 1 "A.cpp" #include using namespace std; using ll = long long; #define endl "\n" void print(){ cout << '\n'; } template void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << ' '; print(forward(tail)...); } template void print(vector &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << ' '; } } template void prisep(vector &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << sep; } } template void print(vector> &A){ for(auto &row: A) print(row); } #line 3 "Library/C++/data_structure/RollbackUnionFind.hpp" using namespace std; struct RollbackUnionFind{ int n; vector par; int group; stack> history; int inner_snap; RollbackUnionFind(int n) : n(n){ par.assign(n, -1); group = n; inner_snap = 0; } int find(int x){ if(par[x] < 0) return x; else return find(par[x]); } bool unite(int x, int y){ x = find(x); y = find(y); history.push({x, par[x]}); history.push({y, par[y]}); if(x == y) return false; if(par[x] > par[y]) swap(x, y); group--; par[x] += par[y]; par[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -par[find(x)]; } vector roots(){ vector ret; for(int i = 0; i < n; i++){ if(i == find(i)) ret.push_back(i); } return ret; } void undo(){ pair tmp = history.top(); history.pop(); int x = tmp.first; par[tmp.first] = tmp.second; tmp = history.top(); history.pop(); par[tmp.first] = tmp.second; if(x != tmp.first) group++; } void snapshot(){ inner_snap = (history.size()) >> 1; } int get_state(){ return (history.size()) >> 1; } void rollback(int state=-1){ if(state == -1) state = inner_snap; state <<= 1; assert(state <= history.size()); while(state < history.size()) undo(); } }; #line 43 "A.cpp" void solve(){ int n, d, w; cin >> n >> d >> w; RollbackUnionFind UF1(n); RollbackUnionFind UF2(n); int a, b; for(int i = 0; i < d; i++){ cin >> a >> b; UF1.unite(a - 1, b - 1); } for(int i = 0; i < w; i++){ cin >> a >> b; UF2.unite(a - 1, b - 1); } int ans = -n; map> mp; for(int i = 0; i < n; i++){ mp[UF1.find(i)].push_back(i); } for(auto tmp:mp){ auto group = tmp.second; int u = group[0]; int ver = UF2.get_state(); for(auto v:group){ if(u == v) continue; UF2.unite(u, v); } ans += UF1.size(u) * UF2.size(u); UF2.rollback(ver); } print(ans); } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); return 0; }