#![allow(unused_imports)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::io::Write; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::(); let (n, m, q) = (v[0], v[1], v[2]); let mut edges = vec![vec![]; n]; let mut uft = UnionFindTree::new(n); for _ in 0..m { let v = read_vec::(); let (a, b) = (v[0] - 1, v[1] - 1); edges[a].push(b); edges[b].push(a); uft.unite(a, b); } let mut used = vec![0; n]; let mut imos = vec![0; n]; let mut same_pairs = HashMap::new(); for _ in 0..q { let v = read_vec::(); let (a, b) = (v[0] - 1, v[1] - 1); if uft.same(a, b) { same_pairs.entry(uft.find(a)).or_insert(vec![]).push((a, b)); } else { used[a] += 1; used[b] += 1; } } let mut roots = HashSet::new(); for i in 0..n { let root = uft.find(i); if edges[root].is_empty() { continue; } roots.insert(root); } let mut ans = 0; let mut lca = LCA::new(&edges); for &root in roots.iter() { if same_pairs.contains_key(&root) { lca.dfs(root, None, 0, &edges); for &(a, b) in same_pairs[&root].iter() { let ca = lca.lca(a, b); ans += (lca.depth[a] + lca.depth[b] - lca.depth[ca]) as i64; } } let mut sum_count = 0; dfs1( root, root, root, &edges, &used, 0, &mut sum_count, &mut imos, ); let mut min_cost = std::i64::MAX; dfs2(root, root, sum_count, &edges, &mut min_cost, &mut imos); ans += min_cost; } println!("{}", ans); } fn dfs1( cur: usize, parent: usize, root: usize, edges: &Vec>, used: &Vec, depth: i64, sum_count: &mut i64, imos: &mut Vec, ) -> i64 { *sum_count += used[cur]; imos[root] += (depth * used[cur]) as i64; let mut k = used[cur]; for &child in edges[cur].iter() { if child == parent { continue; } k += dfs1(child, cur, root, edges, used, depth + 1, sum_count, imos); } if cur != root { imos[cur] = -2 * k; } k } fn dfs2( cur: usize, parent: usize, sum_count: i64, edges: &Vec>, min_cost: &mut i64, imos: &mut Vec, ) { *min_cost = min(*min_cost, imos[cur]); for &child in edges[cur].iter() { if child == parent { continue; } imos[child] += sum_count + imos[cur]; dfs2(child, cur, sum_count, edges, min_cost, imos); } } pub struct LCA { pub depth: Vec, pub parent: Vec>>, } impl LCA { pub fn new(g: &[Vec]) -> LCA { let n = g.len(); let l2 = (1..).find(|i| 1usize << i > n).unwrap(); let depth = vec![0; n]; let parent = vec![vec![None; l2 + 1]; n]; LCA { depth: depth, parent: parent, } } pub fn dfs(&mut self, i: usize, p: Option, d: usize, g: &[Vec]) { self.parent[i][0] = p; self.depth[i] = d; for &t in &g[i] { if Some(t) != p { self.dfs(t, Some(i), d + 1, g); } } } pub fn with_root(root: usize, g: &[Vec]) -> LCA { let n = g.len(); let l2 = (1..).find(|i| 1usize << i > n).unwrap(); let depth = vec![0; n]; let parent = vec![vec![None; l2 + 1]; n]; let mut lca = LCA { depth: depth, parent: parent, }; lca.dfs(root, None, 0, &g); for i in 1..l2 + 1 { for j in 0..n { if let Some(p) = lca.parent[j][i - 1] { lca.parent[j][i] = lca.parent[p][i - 1]; } } } lca } pub fn lca(&self, mut a: usize, mut b: usize) -> usize { use std::mem::swap; if self.depth[b] < self.depth[a] { swap(&mut a, &mut b); } while self.depth[a] != self.depth[b] { b = self.parent[b][(self.depth[b] - self.depth[a]).trailing_zeros() as usize].unwrap(); } if a == b { return a; } for i in (0..self.parent[0].len()).rev() { if self.parent[a][i] != self.parent[b][i] { a = self.parent[a][i].unwrap(); b = self.parent[b][i].unwrap(); } } self.parent[a][0].unwrap() } } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Debug, Clone)] struct UnionFindTree { parent: Vec, size: Vec, height: Vec, } impl UnionFindTree { fn new(n: usize) -> UnionFindTree { UnionFindTree { parent: vec![-1; n], size: vec![1usize; n], height: vec![0u64; n], } } fn find(&mut self, index: usize) -> usize { if self.parent[index] == -1 { return index; } let idx = self.parent[index] as usize; let ret = self.find(idx); self.parent[index] = ret as isize; ret } fn same(&mut self, x: usize, y: usize) -> bool { self.find(x) == self.find(y) } fn get_size(&mut self, x: usize) -> usize { let idx = self.find(x); self.size[idx] } fn unite(&mut self, index0: usize, index1: usize) -> bool { let a = self.find(index0); let b = self.find(index1); if a == b { false } else { if self.height[a] > self.height[b] { self.parent[b] = a as isize; self.size[a] += self.size[b]; } else if self.height[a] < self.height[b] { self.parent[a] = b as isize; self.size[b] += self.size[a]; } else { self.parent[b] = a as isize; self.size[a] += self.size[b]; self.height[a] += 1; } true } } }