use std::io::{BufRead, BufWriter, Write, StdinLock, StdoutLock}; fn input(stdin: &mut StdinLock) -> String { let mut input = String::new(); stdin.read_line(&mut input).ok(); input } macro_rules! read { ($stdin:expr, [$t:tt; $n:expr]) => { (0..$n).map(|_| read!($stdin, $t)).collect::>() }; ($stdin:expr, [$t:tt]) => { input($stdin) .split_whitespace() .map(|x| parse!(x, $t)) .collect::>() }; ($stdin:expr, ($($t:tt),*)) => { { let input = input($stdin); let mut iter = input.split_whitespace(); ( $( parse!(iter.next().unwrap(), $t) ),* ) } }; ($stdin:expr, $t:tt) => { parse!(input($stdin).trim(), $t) }; } macro_rules! parse { ($s:expr, chars) => { $s.chars().collect::>() }; ($s:expr, usize1) => { parse!($s, usize) - 1 }; ($s:expr, $t:ty) => { $s.parse::<$t>().unwrap() } } trait ProconWrite { fn writeln(&mut self, x: T); fn writeln_iter(&mut self, iter: I) where I::Item: std::fmt::Display { self.writeln( iter.map(|x| x.to_string()).collect::>().join(" ") ); } } impl ProconWrite for BufWriter> { fn writeln(&mut self, x: T) { writeln!(self, "{}", x).ok(); } } struct Dsu { n: usize, parent_or_size: Vec, } impl Dsu { fn new(n: usize) -> Dsu { Dsu { n, parent_or_size: vec![!1; n] } } fn merge(&mut self, a: usize, b: usize) -> usize { let (mut x, mut y) = (self.leader(a), self.leader(b)); if x == y { return x; } if !self.parent_or_size[x] < !self.parent_or_size[y] { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] -= !self.parent_or_size[y]; self.parent_or_size[y] = x; x } fn leader(&mut self, a: usize) -> usize { if self.parent_or_size[a] >= self.n { return a; } self.parent_or_size[a] = self.leader(self.parent_or_size[a]); self.parent_or_size[a] } fn size(&mut self, a: usize) -> usize { let x = self.leader(a); !self.parent_or_size[x] } } fn solve(stdin: &mut StdinLock, writer: &mut BufWriter) { let (n, d, w) = read!(stdin, (usize, usize, usize)); let mut car_dsu = Dsu::new(n); for _ in 0..d { let (a, b) = read!(stdin, (usize1, usize1)); car_dsu.merge(a, b); } let mut walker_dsu = Dsu::new(n); for _ in 0..w { let (c, d) = read!(stdin, (usize1, usize1)); walker_dsu.merge(c, d); } let mut ans = 0; let mut set = std::collections::HashSet::new(); for i in 0..n { let x = car_dsu.leader(i); let y = walker_dsu.leader(i); if !set.insert((x, y)) { continue; } ans += car_dsu.size(x) * walker_dsu.size(y); } ans -= n; writer.writeln(ans); } fn main() { let stdin = std::io::stdin(); let mut stdin = stdin.lock(); let stdout = std::io::stdout(); let mut writer = BufWriter::new(stdout.lock()); solve(&mut stdin, &mut writer); }