import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int p = Integer.parseInt(sa[1]); int q = Integer.parseInt(sa[2]); DSU uf1 = new DSU(n); Set set1 = new HashSet<>(); for (int i = 0; i < p; i++) { sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]) - 1; int b = Integer.parseInt(sa[1]) - 1; uf1.merge(a, b); set1.add(a); set1.add(b); } DSU uf2 = new DSU(n); Set set2 = new HashSet<>(); for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]) - 1; int b = Integer.parseInt(sa[1]) - 1; uf2.merge(a, b); set2.add(a); set2.add(b); } br.close(); List> g1 = uf1.groups(); List> g2 = uf2.groups(); Map> g22 = new HashMap<>(); for (int i = 0; i < g2.size(); i++) { List list = g2.get(i); Set set = new HashSet<>(); int l = uf2.leader(list.get(0)); for (Integer o : list) { if (!set1.contains(o)) { set.add(o); } } g22.put(l, set); } long ans = 0; for (int i = 0; i < g1.size(); i++) { List list = g1.get(i); if (!set1.contains(list.get(0))) { continue; } Set set = new HashSet<>(); for (int o : list) { set.add(uf2.leader(o)); } long cnt = 0; for (Integer o : set) { cnt += g22.get(o).size(); } ans += (long) list.size() * (list.size() - 1 + cnt); } for (int i = 0; i < g2.size(); i++) { List list = g2.get(i); if (!set2.contains(list.get(0))) { continue; } long size = list.size(); ans += (long) g22.get(uf2.leader(list.get(0))).size() * (size - 1); } System.out.println(ans); } } /** * Disjoint Set Union(Union Find) */ class DSU { private int n; private int[] parentOrSize; private int num; /** * n頂点0辺の無向グラフを作る。
* O(n) * * @param n 頂点数 */ public DSU(int n) { this.n = n; this.parentOrSize = new int[n]; Arrays.fill(parentOrSize, -1); num = n; } /** * 辺(a, b)を足す。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @param b 頂点番号(0≦b<n) * @return 代表元 */ int merge(int a, int b) { assert 0 <= a && a < n : "a=" + a; assert 0 <= b && b < n : "b=" + b; int x = leader(a); int y = leader(b); if (x == y) { return x; } if (-parentOrSize[x] < -parentOrSize[y]) { int tmp = x; x = y; y = tmp; } parentOrSize[x] += parentOrSize[y]; parentOrSize[y] = x; num--; return x; } /** * 頂点a, bが連結かどうか。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @param b 頂点番号(0≦b<n) * @return true:連結 false:非連結 */ boolean same(int a, int b) { assert 0 <= a && a < n : "a=" + a; assert 0 <= b && b < n : "b=" + b; return leader(a) == leader(b); } /** * 頂点aの属する連結成分の代表元を返す。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @return 代表元 */ int leader(int a) { assert 0 <= a && a < n : "a=" + a; if (parentOrSize[a] < 0) { return a; } else { return parentOrSize[a] = leader(parentOrSize[a]); } } /** * 頂点aの属する連結成分の要素数を返す。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @return 要素数 */ int size(int a) { assert 0 <= a && a < n : "a=" + a; return -parentOrSize[leader(a)]; } /** * 連結成分の数を返す。
* O(1) * * @return 連結成分数 */ int num() { return num; } /** * グラフを連結成分に分けた情報を返す。
* O(n) * * @return 「1つの連結成分の頂点番号のリスト」のリスト */ List> groups() { int[] leaderBuf = new int[n]; int[] groupSize = new int[n]; for (int i = 0; i < n; i++) { leaderBuf[i] = leader(i); groupSize[leaderBuf[i]]++; } List> result = new ArrayList<>(n); for (int i = 0; i < n; i++) { result.add(new ArrayList<>(groupSize[i])); } for (int i = 0; i < n; i++) { result.get(leaderBuf[i]).add(i); } result.removeIf(List::isEmpty); return result; } }