class DoublingLCA: def __init__(self, tree, root=None): self.n = len(tree) self.depth = [0] * self.n self.log_size = (self.n).bit_length() self.parent = [[-1] * self.n for i in range(self.log_size)] if root is None: for v in range(self.n): if self.parent[0][v] == -1: self._dfs(v) else: self._dfs(root) for k in range(self.log_size - 1): for v in range(self.n): if self.parent[k][v] == -1: self.parent[k + 1][v] = -1 else: self.parent[k + 1][v] = self.parent[k][self.parent[k][v]] def _dfs(self, rt): stack = [(rt, -1)] while stack: v, par = stack.pop() for chi_v in tree[v]: if chi_v == par: continue self.parent[0][chi_v] = v self.depth[chi_v] = self.depth[v] + 1 stack.append((chi_v, v)) def lca(self, u, v): if self.depth[u] > self.depth[v]: u, v = v, u for k in range(self.log_size): if ((self.depth[v] - self.depth[u]) >> k) & 1: v = self.parent[k][v] if u == v: return u for k in reversed(range(self.log_size)): if self.parent[k][u] != self.parent[k][v]: u = self.parent[k][u] v = self.parent[k][v] return self.parent[0][u] def distance(self, u, v): lca_uv = self.lca(u, v) if lca_uv == -1: return -1 else: return self.depth[u] + self.depth[v] - 2 * self.depth[lca_uv] class UnionFind: def __init__(self, n): self.parent = [-1] * n self.n = n self.cnt = n def root(self, x): if self.parent[x] < 0: return x else: self.parent[x] = self.root(self.parent[x]) return self.parent[x] def merge(self, x, y): x = self.root(x) y = self.root(y) if x == y: return False if self.parent[x] > self.parent[y]: x, y = y, x self.parent[x] += self.parent[y] self.parent[y] = x self.cnt -= 1 return True def same(self, x, y): return self.root(x) == self.root(y) def size(self, x): return -self.parent[self.root(x)] def count(self): return self.cnt def groups(self): res = [[] for _ in range(self.n)] for i in range(self.n): res[self.root(i)].append(i) return [group for group in res if group] def rerooting(n, edges, unit, merge, addnode): tree = [[] for i in range(n)] idxs = [[] for i in range(n)] for u, v in edges: idxs[u].append(len(tree[v])) idxs[v].append(len(tree[u])) tree[u].append(v) tree[v].append(u) sub = [[unit] * len(tree[v]) for v in range(n)] noderes = [unit] * n # topological sort tp_order = [] par = [-1] * n for root in range(n): if par[root] != -1: continue stack = [root] while stack: v = stack.pop() tp_order.append(v) for nxt_v in tree[v]: if nxt_v == par[v]: continue par[nxt_v] = v stack.append(nxt_v) # tree DP for v in reversed(tp_order[1:]): res = unit par_idx = -1 for idx, nxt_v in enumerate(tree[v]): if nxt_v == par[v]: par_idx = idx continue res = merge(res, sub[v][idx]) if par_idx != -1: sub[par[v]][idxs[v][par_idx]] = addnode(res, v) # rerooting DP for v in tp_order: acc_back = [unit] * len(tree[v]) for i in reversed(range(1, len(acc_back))): acc_back[i - 1] = merge(sub[v][i], acc_back[i]) acc_front = unit for idx, nxt_v in enumerate(tree[v]): res = addnode(merge(acc_front, acc_back[idx]), v) sub[nxt_v][idxs[v][idx]] = res acc_front = merge(acc_front, sub[v][idx]) noderes[v] = addnode(acc_front, v) return noderes n, m, q = map(int, input().split()) edges = [list(map(int, input().split())) for i in range(m)] queries = [list(map(int, input().split())) for i in range(q)] tree = [[] for i in range(n)] uf = UnionFind(n) for i, (u, v) in enumerate(edges): u -= 1 v -= 1 tree[u].append(v) tree[v].append(u) uf.merge(u, v) edges[i] = (u, v) ans = 0 weights = [0] * n db = DoublingLCA(tree) for u, v in queries: u -= 1 v -= 1 dist = db.distance(u, v) if dist == -1: weights[u] += 1 weights[v] += 1 else: ans += dist unit = (0, 0) merge = lambda x1, x2: (x1[0] + x2[0], x1[1] + x2[1]) addnode = lambda x1, v: (x1[0] + weights[v], x1[0] + x1[1]) res = rerooting(n, edges, unit, merge, addnode) for gp in uf.groups(): min_cost = 10 ** 9 for i in gp: min_cost = min(res[i][1], min_cost) ans += min_cost print(ans)