fn main() { let (n, e, ask) = read(); let graph = CSR::new(n, e.iter().flat_map(|e| [(e.0, e.1), (e.1, e.0)])); let mut ord = vec![n; n]; let mut low = vec![n; n]; let mut dsu = DSU::new(n); let mut id = 0; for i in 0..n { if id < ord[i] { dfs(i, n, &graph, &mut ord, &mut low, &mut id, &mut dsu); } } let mut out = String::new(); use std::fmt::*; for (a, b) in ask { let mut ans = "No"; if dsu.same(a, b) { ans = "Yes"; } writeln!(&mut out, "{}", ans).ok(); } print!("{}", out); } fn dfs(v: usize, p: usize, graph: &CSR, ord: &mut [usize], low: &mut [usize], id: &mut usize, dsu: &mut DSU) { ord[v] = *id; low[v] = *id; *id += 1; for u in graph.list(v) { if u == p { continue; } if ord[u] > *id { dfs(u, v, graph, ord, low, id, dsu); low[v] = low[v].min(low[u]); if ord[v] < low[u] { dsu.unite(v, u); } } else { low[v] = low[v].min(ord[u]); } } } fn read() -> (usize, Vec<(usize, usize)>, Vec<(usize, usize)>) { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::()); let mut next = || it.next().unwrap(); let n = next(); let m = next(); let q = next(); let e = (0..m).map(|_| (next() - 1, next() - 1)).collect(); let ask = (0..q).map(|_| (next() - 1, next() - 1)).collect(); (n, e, ask) } // ---------- begin CSR ---------- pub struct CSR { size: usize, pos: Vec, list: Vec, } impl CSR { pub fn new(size: usize, it: I) -> Self where I: Iterator + Clone, { let mut pos = vec![0; size + 1]; for (s, t) in it.clone() { assert!(s < size && t < size); pos[s + 1] += 1; } for i in 1..=size { pos[i] += pos[i - 1]; } let mut x = pos[..size].to_vec(); let mut list = vec![0; pos[size] as usize]; for (s, t) in it { let x = &mut x[s]; list[*x as usize] = t as u32; *x += 1; } CSR { size, pos, list } } pub fn list(&self, v: usize) -> impl Iterator + '_ { assert!(v < self.size); let s = self.pos[v] as usize; let t = self.pos[v + 1] as usize; self.list[s..t].iter().map(|p| *p as usize) } } // ---------- end CSR ---------- //---------- begin union_find ---------- pub struct DSU { p: Vec, } impl DSU { pub fn new(n: usize) -> DSU { assert!(n < std::i32::MAX as usize); DSU { p: vec![-1; n] } } pub fn init(&mut self) { self.p.iter_mut().for_each(|p| *p = -1); } pub fn root(&self, mut x: usize) -> usize { assert!(x < self.p.len()); while self.p[x] >= 0 { x = self.p[x] as usize; } x } pub fn same(&self, x: usize, y: usize) -> bool { assert!(x < self.p.len() && y < self.p.len()); self.root(x) == self.root(y) } pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> { assert!(x < self.p.len() && y < self.p.len()); let mut x = self.root(x); let mut y = self.root(y); if x == y { return None; } if self.p[x] > self.p[y] { std::mem::swap(&mut x, &mut y); } self.p[x] += self.p[y]; self.p[y] = x as i32; Some((x, y)) } } //---------- end union_find ----------