#[allow(dead_code)] #[allow(unused_imports)] fn read() -> T { use std::io::*; let stdin = stdin(); let stdin = stdin.lock(); let token: String = stdin .bytes() .map(|c| c.expect("failed to read char") as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect(); token.parse().ok().expect("failed to parse token") } use std::mem::*; struct UnionFind { par: Vec, } #[allow(dead_code)] impl UnionFind { pub fn new(n: usize) -> Self { let par = (0..n).map(|_| -1).collect(); Self{par} } pub fn root(&mut self, x: usize) -> i64 { if self.par[x] < 0{ x as i64 }else{ self.par[x] = self.root(self.par[x] as usize); self.par[x] } } pub fn same(&mut self, x: usize, y: usize) -> bool { self.root(x) == self.root(y) } pub fn merge(&mut self, x: usize, y: usize) -> bool { let mut _x: i64 = self.root(x); let mut _y: i64 = self.root(y); if _x == _y { return false; } if self.par[_x as usize] > self.par[_y as usize] { swap(&mut _x, &mut _y); } self.par[_x as usize] += self.par[_y as usize]; self.par[_y as usize] = _x as i64; return true; } pub fn size(&mut self, x: usize) -> i64 { (self.par[x]) as i64 * -1 } } fn main(){ let n:usize = read(); let m:usize = read(); let bc:Vec<(usize,usize)> = (0..n).map(|_| (read(),read())).collect(); let mut rec = vec![Vec::new();n]; let mut uf = UnionFind::new(m); for i in 0..n { rec[bc[i].1 - 1].push(bc[i].0 - 1); } let mut ans = 0; for i in 0..n { if rec[i].len() == 0 { continue; } let key = rec[i][0]; for j in 0..rec[i].len() { if !uf.same(key,rec[i][j]) { ans += 1; uf.merge(key,rec[i][j]); } } } println!("{}",ans); }