use std::collections::HashSet; use std::io::{self, BufRead}; use std::mem::swap; struct UnionFind{ parent: Vec, num: Vec, } impl UnionFind{ fn new(n: usize)->Self{ let parent = (0..n).into_iter().collect(); let num = vec![1; n]; UnionFind{ parent, num, } } fn find(&mut self, x: usize)->usize{ if x==self.parent[x]{return x;} self.parent[x] = self.find(self.parent[x]); self.parent[x] } fn union(&mut self, u: usize, v: usize){ let (mut pu, mut pv) = (self.find(u), self.find(v)); if pu==pv{return;} if self.num[pu] < self.num[pv]{ swap(&mut pu, &mut pv); } self.num[pu] += self.num[pv]; self.parent[pv] = pu; } fn same(&mut self, u: usize, v: usize)->bool{ self.find(u)==self.find(v) } } struct CycleFinder { n: usize, edge: Vec>, went: Vec, used: Vec, cycle: Vec, way: Vec, cycle_edge: HashSet<(usize, usize)>, } impl CycleFinder{ fn new(n: usize)->Self{ let edge = vec![Vec::new(); n]; let went = vec![false; n]; let used = vec![false; n]; let cycle = vec![false; n]; let way = Vec::new(); let cycle_edge = HashSet::new(); CycleFinder{n, edge, went, used, cycle, way, cycle_edge} } fn add_edge(&mut self, u: usize, v: usize){ assert!(u < self.n && v < self.n); self.edge[u].push(v); self.edge[v].push(u); } fn build(&mut self){ for i in 0..self.n{ if self.used[i]{continue} self._dfs(i, !0); } } fn _dfs(&mut self, x: usize, pre: usize) { self.went[x] = true; self.way.push(x); let edges_ptr = self.edge[x].as_ptr(); let edges_len = self.edge[x].len(); for i in 0..edges_len { let nex = unsafe { *edges_ptr.add(i) }; if self.used[nex] || nex==pre{ continue; } if self.went[nex] { let t = nex; let mut p = self.way.len() - 1; self.cycle_edge.insert((self.way[p], t)); while self.way[p] != t { self.cycle[self.way[p]] = true; p -= 1; self.cycle_edge.insert((self.way[p], self.way[p+1])); } self.cycle[t] = true; } else { self._dfs(nex, x); } } self.used[x] = true; self.way.pop(); } fn include_cycle(&self)->HashSet<(usize, usize)>{ self.cycle_edge.clone() } } fn main() { //input! { // n: usize, m: usize, q: usize, // e: [(usize, usize); m], // query: [(usize, usize); q] //} //ここからの入力はgptです…やりたいことはただ以上のようなものです。 let stdin = io::stdin(); let mut iterator = stdin.lock().lines(); let first_line = iterator.next().unwrap().unwrap(); let mut iter = first_line.split_whitespace(); let n: usize = iter.next().unwrap().parse().unwrap(); let m: usize = iter.next().unwrap().parse().unwrap(); let q: usize = iter.next().unwrap().parse().unwrap(); let mut e = Vec::with_capacity(m); for _ in 0..m { let line = iterator.next().unwrap().unwrap(); let mut iter = line.split_whitespace(); let u: usize = iter.next().unwrap().parse().unwrap(); let v: usize = iter.next().unwrap().parse().unwrap(); e.push((u, v)); } let mut query = Vec::with_capacity(q); for _ in 0..q { let line = iterator.next().unwrap().unwrap(); let mut iter = line.split_whitespace(); let u: usize = iter.next().unwrap().parse().unwrap(); let v: usize = iter.next().unwrap().parse().unwrap(); query.push((u, v)); } //↑ここまでの入力はgptです。 let mut cf = CycleFinder::new(n); for &(u, v) in &e{ cf.add_edge(u-1, v-1); } cf.build(); let cycle = cf.include_cycle(); let mut uf = UnionFind::new(n); for &(u, v) in &e{ if !cycle.contains(&(u-1, v-1))&&!cycle.contains(&(v-1, u-1)){ uf.union(u-1, v-1); } } for &(u, v) in &query{ if uf.same(u-1, v-1){ println!("Yes"); } else { println!("No"); } } }