mod io { #[macro_export] macro_rules! scan { ($r:expr, [$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($r, $t)).collect::>()); ($r:expr, ($($t:tt),*)) => (($(scan!($r, $t)),*)); ($r:expr, [u8]) => (io::scan($r).into_bytes()); ($r:expr, $t:ty) => (io::scan($r).parse::<$t>().unwrap()); } use std::io::{BufRead, ErrorKind}; pub fn scan(r: &mut R) -> String { let mut res = Vec::new(); loop { let buf = match r.fill_buf() { Ok(buf) => buf, Err(e) if e.kind() == ErrorKind::Interrupted => continue, Err(e) => panic!(e), }; let (done, used) = match buf.iter().position(u8::is_ascii_whitespace) { Some(i) => { res.extend_from_slice(&buf[..i]); (res.len() > 0, i + 1) } None => { res.extend_from_slice(buf); (false, buf.len()) } }; r.consume(used); if done || used == 0 { return res.into_iter().map(char::from).collect(); } } } } #[allow(dead_code)] mod dsu { // reference: https://github.com/atcoder/ac-library pub struct Dsu { n: usize, parent_or_size: Vec, } impl Dsu { pub fn new(n: usize) -> Dsu { Dsu { n, parent_or_size: vec![!1; n] } } pub fn merge(&mut self, a: usize, b: usize) -> usize { let (mut x, mut y) = (self.leader(a), self.leader(b)); if x == y { return x; } if !self.parent_or_size[x] < !self.parent_or_size[y] { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] -= !self.parent_or_size[y]; self.parent_or_size[y] = x; x } pub fn same(&mut self, a: usize, b: usize) -> bool { self.leader(a) == self.leader(b) } pub fn leader(&mut self, a: usize) -> usize { if self.parent_or_size[a] >= self.n { return a; } self.parent_or_size[a] = self.leader(self.parent_or_size[a]); self.parent_or_size[a] } pub fn size(&mut self, a: usize) -> usize { let x = self.leader(a); !self.parent_or_size[x] } } } use std::io::{BufRead, Write}; use dsu::Dsu; fn run(reader: &mut R, writer: &mut W) { let (n, m) = scan!(reader, (usize, usize)); let mut dsu = Dsu::new(m + 1); let mut colors = vec![0; n + 1]; for _ in 0..n { let (b, c) = scan!(reader, (usize, usize)); if colors[c] > 0 { dsu.merge(colors[c], b); } colors[c] = b; } let mut ans = 0; for i in 1..=m { if i == dsu.leader(i) { ans += dsu.size(i) - 1; } } writeln!(writer, "{}", ans).ok(); } fn main() { let (stdin, stdout) = (std::io::stdin(), std::io::stdout()); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); run(&mut reader, &mut writer); }