pub use __cargo_equip::prelude::*; use scanner::Scanner; use std::io; use union_find::UnionFind; fn main() { let mut scanner = Scanner::from(io::stdin().lock()); let (n, m) = scan!((usize, usize), <~ scanner); let c = scan!([usize; n], <~ scanner); let edges = scan!([(usize, usize); m], <~ scanner); let c = c.into_iter().map(|c| c - 1).collect::>(); let edges = edges .into_iter() .map(|(u, v)| (u - 1, v - 1)) .collect::>(); let mut sets = vec![vec![]; n]; for i in 0..n { sets[c[i]].push(i); } let mut uf = UnionFind::new(n); for (u, v) in edges { if sets[c[u]].contains(&v) { uf.unite(u, v); } } let mut ans = 0; for set in sets { if set.is_empty() { continue; } let mut roots = Vec::new(); for v in set { roots.push(uf.find(v)); } roots.sort(); roots.dedup(); assert!(roots.len() >= 1); ans += roots.len() - 1; } println!("{}", ans); } // ✂ --- scanner --- ✂ #[allow(unused)] mod scanner { pub use crate::__cargo_equip::prelude::*; use std::fmt; use std::io; use std::str; pub struct Scanner { r: R, l: String, i: usize, } impl Scanner where R: io::BufRead, { pub fn new(reader: R) -> Self { Self { r: reader, l: String::new(), i: 0, } } pub fn scan(&mut self) -> T where T: str::FromStr, T::Err: fmt::Debug, { self.skip_blanks(); assert!(self.i < self.l.len()); // remain some character assert_ne!(&self.l[self.i..=self.i], " "); let rest = &self.l[self.i..]; let len = rest .find(|ch| char::is_ascii_whitespace(&ch)) .unwrap_or_else(|| rest.len()); // parse self.l[self.i..(self.i + len)] let val = rest[..len] .parse() .unwrap_or_else(|e| panic!("{:?}, attempt to read `{}`", e, rest)); self.i += len; val } pub fn scan_vec(&mut self, n: usize) -> Vec where T: str::FromStr, T::Err: fmt::Debug, { (0..n).map(|_| self.scan()).collect::>() } fn skip_blanks(&mut self) { loop { match self.l[self.i..].find(|ch| !char::is_ascii_whitespace(&ch)) { Some(j) => { self.i += j; break; } None => { self.l.clear(); // clear buffer let num_bytes = self .r .read_line(&mut self.l) .unwrap_or_else(|_| panic!("invalid UTF-8")); assert!(num_bytes > 0, "reached EOF :("); self.i = 0; } } } } } impl<'a> From<&'a str> for Scanner<&'a [u8]> { fn from(s: &'a str) -> Self { Self::new(s.as_bytes()) } } impl<'a> From> for Scanner>> { fn from(stdin: io::StdinLock<'a>) -> Self { Self::new(io::BufReader::new(stdin)) } } #[macro_export] macro_rules! scan { (( $($t: ty),+ ), <~ $scanner: expr) => { ( $(scan!($t, <~ $scanner)),+ ) }; ([ $t: tt; $n: expr ], <~ $scanner: expr) => { (0..$n).map(|_| scan!($t, <~ $scanner)).collect::>() }; ($t: ty, <~ $scanner: expr) => { $scanner.scan::<$t>() }; } } // ✂ --- scanner --- ✂ // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `union_find 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#f49de25336b2de6602bce284a44ec4b9d163e9f4)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::union_find` #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod union_find { pub struct UnionFind { par: Vec, size: Vec, } impl UnionFind { pub fn new(n: usize) -> UnionFind { UnionFind { par: (0..n).collect(), size: vec![1; n], } } pub fn find(&mut self, i: usize) -> usize { if self.par[i] != i { self.par[i] = self.find(self.par[i]); } self.par[i] } pub fn unite(&mut self, i: usize, j: usize) { let i = self.find(i); let j = self.find(j); if i == j { return; } let (i, j) = if self.size[i] >= self.size[j] { (i, j) } else { (j, i) }; self.par[j] = i; self.size[i] += self.size[j]; } pub fn get_size(&mut self, i: usize) -> usize { let p = self.find(i); self.size[p] } pub fn same(&mut self, i: usize, j: usize) -> bool { self.find(i) == self.find(j) } } } } pub(crate) mod macros { pub mod union_find {} } pub(crate) mod prelude { pub use crate::__cargo_equip::crates::*; } mod preludes { pub mod union_find {} } }