## https://yukicoder.me/problems/no/1293 class UnionFind: """ UnionFindの基本的な処理を実装したクラス """ def __init__(self, size): self.root = [i for i in range(size)] self.size = [1] * size def get_root(self, v): if v == self.root[v]: return v else: old_root = self.root[v] new_root = self.get_root(old_root) self.root[v] = new_root return new_root def merge(self, u, v): root_u = self.get_root(u) root_v = self.get_root(v) if root_u == root_v: return False if self.size[root_u] >= self.size[root_v]: self.size[root_u] += self.size[root_v] self.root[root_v] = root_u self.root[v] = root_u else: self.size[root_v] += self.size[root_u] self.root[root_u] = root_v self.root[u] = root_v return True def main(): N, D, W = map(int, input().split()) ab = [] for _ in range(D): a, b = map(int ,input().split()) ab.append((a - 1, b - 1)) cd = [] for _ in range(W): c, d = map(int, input().split()) cd.append((c - 1, d - 1)) # walk側のUnionFind uf_walk = UnionFind(N) for c ,d in cd: uf_walk.merge(c, d) # drive側 uf_drive = UnionFind(N) for a, b in ab: uf_drive.merge(a, b) uf_comps = {} for i in range(N): r_i = uf_drive.get_root(i) if r_i not in uf_comps: uf_comps[r_i] = [] uf_comps[r_i].append(i) answer = 0 for drive_nodes in uf_comps.values(): n = len(drive_nodes) answer += n ** 2 - n w_map = {} for i in drive_nodes: r_i = uf_walk.get_root(i) if r_i not in w_map: w_map[r_i] = 0 w_map[r_i] += 1 for r_i, m in w_map.items(): r_size = uf_walk.size[r_i] l = r_size - m answer += l * n print(answer) if __name__ == "__main__": main()