use std::collections::*; use std::io::{Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } /** * Dinic's algorithm for maximum flow problem. * Verified by: yukicoder No.177 (http://yukicoder.me/submissions/148371) * Min-cut (the second element of max_flow's returned values) is not verified. */ #[derive(Clone)] struct Edge { to: usize, cap: T, rev: usize, // rev is the position of the reverse edge in graph[to] } struct Dinic { graph: Vec>>, iter: Vec, zero: T, } impl Dinic where T: Clone, T: Copy, T: Ord, T: std::ops::AddAssign, T: std::ops::SubAssign, { fn bfs(&self, s: usize, level: &mut [Option]) { let n = level.len(); for i in 0 .. n { level[i] = None; } let mut que = std::collections::VecDeque::new(); level[s] = Some(0); que.push_back(s); while let Some(v) = que.pop_front() { for e in self.graph[v].iter() { if e.cap > self.zero && level[e.to] == None { level[e.to] = Some(level[v].unwrap() + 1); que.push_back(e.to); } } } } /* search augment path by dfs. * if f == None, f is treated as infinity. */ fn dfs(&mut self, v: usize, t: usize, f: Option, level: &mut [Option]) -> T { if v == t { return f.unwrap(); } while self.iter[v] < self.graph[v].len() { let i = self.iter[v]; let e = self.graph[v][i].clone(); if e.cap > self.zero && level[v] < level[e.to] { let newf = std::cmp::min(f.unwrap_or(e.cap), e.cap); let d = self.dfs(e.to, t, Some(newf), level); if d > self.zero { self.graph[v][i].cap -= d; self.graph[e.to][e.rev].cap += d; return d; } } self.iter[v] += 1; } self.zero } pub fn new(n: usize, zero: T) -> Self { Dinic { graph: vec![Vec::new(); n], iter: vec![0; n], zero: zero, } } pub fn add_edge(&mut self, from: usize, to: usize, cap: T) { let added_from = Edge { to: to, cap: cap, rev: self.graph[to].len() }; let added_to = Edge { to: from, cap: self.zero, rev: self.graph[from].len() }; self.graph[from].push(added_from); self.graph[to].push(added_to); } pub fn max_flow(&mut self, s: usize, t: usize) -> (T, Vec) { let mut flow = self.zero; let n = self.graph.len(); let mut level = vec![None; n]; loop { self.bfs(s, &mut level); if level[t] == None { let ret = (0 .. n).filter(|&i| level[i] == None) .collect(); return (flow, ret); } self.iter.clear(); self.iter.resize(n, 0); loop { let f = self.dfs(s, t, None, &mut level); if f <= self.zero { break; } flow += f; } } } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););} input! { n: usize, m: usize, l: usize, ab: [(usize1, usize1); l], } let mut din = Dinic::new(2 + n + m, 0); for i in 0..n { din.add_edge(0, 2 + i, 1); } for i in 0..m { din.add_edge(2 + n + i, 1, 1); } for &(a, b) in &ab { din.add_edge(2 + a, 2 + n + b, 1); } let _ = din.max_flow(0, 1); let mut to = vec![None; n]; let mut used = vec![false; m]; for i in 0..m { for e in &din.graph[2 + n + i] { if e.to >= 2 && e.cap == 1 { to[e.to - 2] = Some(i); used[i] = true; } } } for i in 0..l { let (a, b) = ab[i]; if to[a] != Some(b) { puts!("Yes\n"); continue; } let mut g = vec![vec![]; 2 + n + m]; for i in 0..n { if to[i].is_some() { g[2 + i].push(0); } else { g[0].push(2 + i); } } for i in 0..m { if used[i] { g[1].push(2 + n + i); } else { g[2 + n + i].push(1); } } for j in 0..l { if i == j { continue; } let (c, d) = ab[j]; if to[c] == Some(d) { g[2 + n + d].push(2 + c); } else { g[2 + c].push(2 + n + d); } } let mut que = VecDeque::new(); let mut vis = vec![false; 2 + n + m]; que.push_back(2 + a); while let Some(v) = que.pop_front() { if vis[v] { continue; } vis[v] = true; for &w in &g[v] { if !vis[w] { que.push_back(w); } } } puts!("{}\n", if vis[2 + n + b] { "Yes" } else { "No" }); } }