use atcoder8_library::{scc::SCC, union_find::UnionFind}; 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 node_num = unzip.len(); let mut uf = UnionFind::new(node_num); let mut indegree = vec![0; node_num]; let mut outdegree = vec![0; node_num]; for &(h, w) in &zip_hw { indegree[w] += 1; outdegree[h] += 1; uf.merge(h, w); } if uf.group_num() != 1 { println!("0"); std::process::exit(0); } let same_num = (0..node_num) .filter(|&i| indegree[i] == outdegree[i]) .count(); if same_num == node_num { println!("{}", n); } else if same_num == node_num - 2 && (0..node_num) .filter(|&i| indegree[i] + 1 == outdegree[i]) .count() == 1 && (0..node_num) .filter(|&i| indegree[i] == outdegree[i] + 1) .count() == 1 { println!("1"); } 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 union_find { //! Union-Find processes the following queries on undirected graphs. //! * Merge two connected components. //! * Determine whether two given nodes are in the same connected component. //! //! To seed up processing, merge optimization using the number of nodes //! of the connected components and path compression are performed. //! //! The time complexity of each query is `O(A(n))`. //! where `n` is the number of nodes in the graph and //! `A(n)` is the inverse of the Ackermann function. /// This is the value that will be associated with each nodes of the graph. #[derive(Debug, Clone, Copy)] enum ParentOrSize { /// It is used for non-representative nodes and stores the parent node. Parent(usize), /// It is used for the representative node and /// stores the number of nodes of the connected component. Size(usize), } /// Union-Find processes the following queries on undirected graphs. /// * Merge two connected components. /// * Determine whether two given nodes are in the same connected component. /// /// To seed up processing, merge optimization using the number of nodes /// of the connected components and path compression are performed. /// /// The time complexity of each query is `O(A(n))`. /// where `n` is the number of nodes in the graph and /// `A(n)` is the inverse of the Ackermann function. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(0, 1); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(1, 2); /// assert_eq!(uf.same(0, 2), true); /// ``` #[derive(Debug, Default, Clone)] pub struct UnionFind { /// For each node, one of the following is stored. /// * The number of nodes of the connected component to which it belongs. /// (If it is a representative node of the connected component.) /// * Index of the parent node. (Otherwise.) parent_or_size: Vec, /// Number of connected components. group_num: usize, } impl UnionFind { /// Create an undirected graph with `n` nodes and `0` edges. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(0, 1); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(2, 1); /// assert_eq!(uf.same(0, 2), true); /// ``` pub fn new(n: usize) -> Self { UnionFind { parent_or_size: vec![ParentOrSize::Size(1); n], group_num: n, } } /// Return the representative node of the connected component containing node `a`. /// /// At that time, perform path compression on the nodes on the path from node `a` to the representative node. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// uf.merge(1, 2); /// assert_eq!(uf.leader(0), 0); /// assert_eq!(uf.leader(1), uf.leader(2)); /// ``` pub fn leader(&mut self, a: usize) -> usize { // If node `a` is a representative node of the connected component, return `a`. if let ParentOrSize::Size(_) = self.parent_or_size[a] { return a; } // Path from node `a` to the representative node. let mut path = vec![]; // Current node. let mut current = a; // Record the path to the representative node. while let ParentOrSize::Parent(parent) = self.parent_or_size[current] { // Add current node to the path. path.push(current); // Move to the parent node. current = parent; } // The representative node of the connected component. let leader = current; // Set nodes on the path as direct children of the representative node. path.iter().for_each(|&node| { self.parent_or_size[node] = ParentOrSize::Parent(leader); }); // Return the representative node of the connected component. leader } /// Return whether two nodes `a` and `b` are in the same connected component. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(0, 1); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(2, 1); /// assert_eq!(uf.same(0, 2), true); /// ``` pub fn same(&mut self, a: usize, b: usize) -> bool { self.leader(a) == self.leader(b) } /// Merge each connected component containing nodes `a` and `b`. /// /// Return `true` if different connected components are newly merged. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(0, 1); /// assert_eq!(uf.same(0, 2), false); /// uf.merge(2, 1); /// assert_eq!(uf.same(0, 2), true); /// ``` pub fn merge(&mut self, a: usize, b: usize) -> bool { // Representative node of the connected component that contains the node `a`. let leader_a = self.leader(a); // Representative node of the connected component that contains the node `b`. let leader_b = self.leader(b); // If nodes `a` and `b` are in the same connected component, return `false` without processing. if leader_a == leader_b { return false; } // Number of nodes of the component containing node `a`. let component_size_a = self.size(leader_a); // Number of nodes of the component containing node `b`. let component_size_b = self.size(leader_b); // Number of nodes of the merged component. let merged_component_size = component_size_a + component_size_b; // Set the parent of the representative node of the smaller sized connected component // to be the parent of the other connected component. if component_size_a <= component_size_b { self.parent_or_size[leader_a] = ParentOrSize::Parent(leader_b); self.parent_or_size[leader_b] = ParentOrSize::Size(merged_component_size); } else { self.parent_or_size[leader_b] = ParentOrSize::Parent(leader_a); self.parent_or_size[leader_a] = ParentOrSize::Size(merged_component_size); } // Decrease the number of connected components by one. self.group_num -= 1; // Return `true` because different connected components are newly combined. true } /// Return a list of connected components. /// /// Each connected component consists of indexes of nodes. /// The indexes of the nodes in each connected component are arranged in ascending order. /// The list of connected components is sorted in ascending order /// with respect to the smallest index of the included nodes. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(5); /// uf.merge(1, 2); /// uf.merge(2, 3); /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3], vec![4]]); /// ``` pub fn groups(&mut self) -> Vec> { // Number of nodes in graph. let element_num = self.parent_or_size.len(); // List of connected components. let mut groups: Vec> = vec![]; // Correspondence between the representative node and group index. let mut leader_to_idx: Vec> = vec![None; element_num]; // Assign each node in the graph to a group. for node in 0..element_num { // Representative node of the connected component to which the `node` belongs. let leader = self.leader(node); if let Some(group_idx) = leader_to_idx[leader] { // Assign to an existing group. groups[group_idx].push(node); } else { // Adding a new group. leader_to_idx[leader] = Some(groups.len()); groups.push(vec![node]); } } // Return a list of groups. groups } /// Return the number of nodes in the connected component to which node `a` belongs. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// assert_eq!(uf.size(0), 1); /// uf.merge(0, 1); /// assert_eq!(uf.size(0), 2); /// uf.merge(2, 1); /// assert_eq!(uf.size(0), 3); /// ``` pub fn size(&mut self, a: usize) -> usize { let leader = self.leader(a); match self.parent_or_size[leader] { ParentOrSize::Parent(_) => panic!(), ParentOrSize::Size(size) => size, } } /// Add a new node with degree `0`. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(4); /// uf.merge(1, 2); /// uf.merge(2, 3); /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3]]); /// uf.add(); /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3], vec![4]]); /// ``` pub fn add(&mut self) { self.parent_or_size.push(ParentOrSize::Size(1)); self.group_num += 1; } /// Return the number of connected components. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(3); /// assert_eq!(uf.group_num(), 3); /// uf.merge(0, 1); /// assert_eq!(uf.group_num(), 2); /// uf.merge(2, 1); /// assert_eq!(uf.group_num(), 1); /// ``` pub fn group_num(&self) -> usize { self.group_num } /// Return the number of nodes in the graph. /// /// # Examples /// /// ``` /// use atcoder8_library::union_find::UnionFind; /// /// let mut uf = UnionFind::new(5); /// assert_eq!(uf.elem_num(), 5); /// ``` pub fn elem_num(&self) -> usize { self.parent_or_size.len() } } } 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 } } }