#include #include using namespace std; typedef unsigned long long _ulong; typedef long long int lint; typedef pair plint; typedef pair pld; #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((lint)(x).size()) #define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) #define endk '\n' templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } lint gcd(lint a, lint b) { if (b == 0) return a; else return gcd(b, a % b); } lint ceil(lint a, lint b) { return (a + b - 1) / b; } lint digit(lint a) { return (lint)log10(a); } const lint MOD = 1e9 + 7, INF = 1e18; lint dx[8] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[8] = { 0, 1, 0, -1, -1, -1, 1, 1 }; void YN(bool flag) { cout << (flag ? "YES" : "NO") << endk; } typedef pair Pa; typedef pair tlint; template< typename T > class UnionFind { public: vector par; // 各元の親を表す配列 vector siz; // 素集合のサイズを表す配列(1 で初期化) // Constructor UnionFind(T sz_) : par(sz_), siz(sz_, 1ll) { for (T i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } void init(T sz_) { par.resize(sz_); siz.assign(sz_, 1ll); // resize だとなぜか初期化されなかった for (T i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } // Member Function // Find T root(T x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } // Union(Unite, Merge) bool merge(T x, T y) { x = root(x); y = root(y); if (x == y) return false; // merge technique(データ構造をマージするテク.小を大にくっつける) if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool issame(T x, T y) { // 連結判定 return root(x) == root(y); } T size(T x) { // 素集合のサイズ return siz[root(x)]; } }; lint N, D, W, u, v; int main() { cin >> N >> D >> W; UnionFind drive(N), walk(N); vector edges(W); REP(i, D) { cin >> u >> v; u--; v--; drive.merge(u, v); } REP(i, W) { cin >> u >> v; u--; v--; walk.merge(u, v); } lint ans = 0; set used; REP(i, N) { plint p = { drive.root(i), walk.root(i) }; if (!used.count(p)) { ans += drive.size(i) * walk.size(i); used.insert(p); } } cout << ans - N << endk; }