use atcoder8_library::scc::SCC; fn main() { let n = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse::().unwrap() }; let mut hw = Vec::new(); for _ in 0..n { hw.push({ let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::().unwrap() - 1, iter.next().unwrap().parse::().unwrap() - 1, ) }); } let values: Vec = hw .iter() .map(|x| x.0) .chain(hw.iter().map(|x| x.1)) .collect(); let (zip, unzip) = coordinate_compression(&values); let zip_hw: Vec<(usize, usize)> = (0..n).map(|i| (zip[i], zip[n + i])).collect(); let mut graph = vec![vec![]; unzip.len()]; for &(h, w) in &zip_hw { graph[h].push(w); } graph.iter_mut().for_each(|x| x.sort_unstable()); let mut scc_graph = SCC::new(unzip.len()); for &(h, w) in &zip_hw { scc_graph.add_edge(h, w); } let scc = scc_graph.scc(); let mut visited = vec![false; unzip.len()]; let mut stack = scc[0].clone(); while let Some(cur) = stack.pop() { if visited[cur] { continue; } visited[cur] = true; for &next in &graph[cur] { stack.push(next); } } if visited.iter().all(|&x| x) { println!("{}", scc.last().unwrap().len()); } else { println!("0"); } } /// Performs coordinate compression of `seq`. /// /// The return value is a tuple of `zip` and `unzip`. /// `zip` is a list of the number of smallest values in the whole sequence for each element. /// `unzip` is a list of the values that appear in the number sequence in ascending order. /// The `i`-th element of the original sequence can be restored by `unzip[zip[i]]`. pub fn coordinate_compression(seq: &[T]) -> (Vec, Vec) where T: Clone + Ord, { let mut unzip = seq.to_owned(); unzip.sort_unstable(); unzip.dedup(); let zip: Vec = seq .iter() .map(|x| unzip.binary_search(x).unwrap()) .collect(); (zip, unzip) } pub mod atcoder8_library { pub mod scc { #[derive(Debug, Clone)] pub struct SCC { graph: Vec>, inv_graph: Vec>, } impl SCC { pub fn new(n: usize) -> Self { Self { graph: vec![vec![]; n], inv_graph: vec![vec![]; n], } } pub fn add_edge(&mut self, from: usize, to: usize) { self.graph[from].push(to); self.inv_graph[to].push(from); } pub fn scc(&self) -> Vec> { let n = self.graph.len(); let mut order = vec![]; let mut visited = vec![false; n]; for start_node in 0..n { if !visited[start_node] { order.append(&mut post_order_traversal( &self.graph, &mut visited, start_node, )); } } let mut scc = vec![]; let mut visited = vec![false; n]; for &start_node in order.iter().rev() { if !visited[start_node] { scc.push(post_order_traversal( &self.inv_graph, &mut visited, start_node, )); } } scc } } fn post_order_traversal( graph: &Vec>, visited: &mut Vec, start_node: usize, ) -> Vec { let mut post_order = vec![]; let mut stack = vec![(start_node, false)]; while let Some((node, back)) = stack.pop() { if back { post_order.push(node); } if visited[node] { continue; } visited[node] = true; stack.push((node, true)); stack.extend(graph[node].iter().map(|&next_node| (next_node, false))); } post_order } } }