#include "bits/stdc++.h" #define MOD 1000000007 #define rep(i, n) for(ll i=0; i < (n); i++) #define rrep(i, n) for(ll i=(n)-1; i >=0; i--) #define ALL(v) v.begin(),v.end() #define rALL(v) v.rbegin(),v.rend() #define FOR(i, j, k) for(ll i=j;i llvec; typedef vector dvec; typedef pair P; typedef long double ld; struct edge{ll x, c;}; struct UnionFind{ ll N; llvec p; llvec cnt; UnionFind(ll n){ N = n; p=llvec(N); cnt=llvec(N, 0); rep(i, N){ p[i] = i; cnt[i] = 1; } } void con(ll a, ll b){ P at = root(a); P bt = root(b); if(at.second!=bt.second){ if(at.first>bt.first){ swap(at, bt); swap(a, b); } p[at.second] = bt.second; cnt[bt.second]+=cnt[at.second]; p[a]=bt.second; } } P root(ll a){ ll atmp = a; ll c=0; while(atmp!=p[atmp]){ atmp = p[atmp]; c++; } p[a] = atmp; return {c, atmp}; } bool is_con(ll a, ll b){ P at=root(a); P bt=root(b); return at.second == bt.second; } }; struct UnionFind2{ ll N; llvec p; llvec cnt; vector> type; UnionFind2(ll n){ N = n; p=llvec(N); cnt=llvec(N, 0); type=vector>(N); rep(i, N){ p[i] = i; cnt[i] = 1; } } void con(ll a, ll b){ P at = root(a); P bt = root(b); if(at.second!=bt.second){ if(cnt[at.se]>cnt[bt.se])swap(at,bt); p[at.second] = bt.second; cnt[bt.second]+=cnt[at.second]; for(auto is: type[at.se]){ type[bt.se].insert(is); } p[a]=bt.second; } } P root(ll a){ ll atmp = a; ll c=0; while(atmp!=p[atmp]){ atmp = p[atmp]; c++; } p[a] = atmp; return {c, atmp}; } bool is_con(ll a, ll b){ P at=root(a); P bt=root(b); return at.second == bt.second; } }; /************************************** ** A main function starts from here ** ***************************************/ int main(){ ll N, D, W; cin >> N >> D >> W; UnionFind uf1(N); UnionFind2 uf2(N); rep(i, D){ ll a, b; cin >> a >> b; a--;b--; uf1.con(a, b); } rep(i, N){ auto p = uf1.root(i); uf2.type[i].insert(p.se); } rep(i, W){ ll a, b; cin >> a >> b; a--;b--; uf2.con(a, b); } ll ans = 0; rep(i, N){ if(uf2.p[i]==i){ for(auto is: uf2.type[i]){ ans = ans + uf1.cnt[is] * uf2.cnt[i]; } } } cout << ans-N << endl; return 0; }