fn solve(_reader: R, _writer: &mut W) { let mut _scanner = Scanner::new(_reader); #[allow(unused_macros)] macro_rules! scan { ($t:ty) => { _scanner.next::<$t>().unwrap() }; ($($t:ty),+) => { ($(scan!($t)),+) }; ($t:ty; $n:expr) => { scan_iter!($t; $n).collect::>() }; ($t_0:ty, $t_1:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1; $n) }; ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n) }; ($($t:ty = $i:tt),+; $n:expr) => {{ let mut vecs = ($(Vec::<$t>::with_capacity($n)),+); for _ in 0..$n {$( vecs.$i.push(scan!($t)); )+} vecs }}; } #[allow(unused_macros)] macro_rules! scan_iter { ($t:ty; $n:expr) => { _scanner.take::<$t>($n).map(|x| x.unwrap()) }; } #[allow(unused_macros)] macro_rules! print { ($fmt:expr) => { write!(_writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { write!(_writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! println { () => { writeln!(_writer).unwrap() }; ($fmt:expr) => { writeln!(_writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { writeln!(_writer, $fmt, $($arg)*).unwrap() }; } use data_structures::UnionFindTree; use std::mem::swap; let (n, m) = scan!(usize, usize); let mut uf = UnionFindTree::new(n); for _ in 0..m { let (mut a, mut b) = scan!(usize, usize); a -= 1; b -= 1; if uf.find(a) > uf.find(b) { swap(&mut a, &mut b); } uf.unite(a, b); } for i in 0..n { println!("{}", uf.find(i) + 1); } } fn main() { let stdin = stdin(); let stdout = stdout(); #[cfg(debug_assertions)] let mut writer = stdout.lock(); #[cfg(not(debug_assertions))] let mut writer = ::std::io::BufWriter::new(stdout.lock()); solve(stdin.lock(), &mut writer); writer.flush().unwrap(); } use io::Scanner; use std::io::{stdin, stdout, BufRead, Write}; pub mod data_structures { pub use self::union_find_tree::*; mod union_find_tree { use std::mem::swap; pub struct UnionFindTree { nodes: Vec, } #[derive(Clone, Copy)] enum Node { Root { node_count: usize }, Descendant { parent_index: usize }, } impl UnionFindTree { pub fn new(size: usize) -> Self { UnionFindTree { nodes: vec![Node::Root { node_count: 1 }; size], } } pub fn len(&self) -> usize { self.nodes.len() } pub fn unite(&mut self, l_index: usize, r_index: usize) -> bool { debug_assert!(l_index < self.len()); debug_assert!(r_index < self.len()); let mut l_root_index = self.find(l_index); let mut r_root_index = self.find(r_index); if l_root_index == r_root_index { return false; } match (self.nodes[l_root_index], self.nodes[r_root_index]) { (Node::Root { node_count: l_node_count }, Node::Root { node_count: r_node_count }) => { let node_count = l_node_count + r_node_count; if l_node_count < r_node_count { swap(&mut l_root_index, &mut r_root_index); } self.nodes[l_root_index] = Node::Root { node_count: node_count }; self.nodes[r_root_index] = Node::Descendant { parent_index: l_root_index }; } _ => unreachable!("`find` must return root index"), } true } pub fn find(&mut self, index: usize) -> usize { debug_assert!(index < self.len()); match self.nodes[index] { Node::Root { .. } => index, Node::Descendant { parent_index } => { let root_index = self.find(parent_index); debug_assert!(match self.nodes[parent_index] { Node::Root { .. } => true, Node::Descendant { parent_index: parent_parent_index } => match self.nodes[parent_parent_index] { Node::Root { .. } => true, Node::Descendant { .. } => false, }, }); self.nodes[index] = Node::Descendant { parent_index: root_index }; root_index } } } pub fn is_same_group(&mut self, l_index: usize, r_index: usize) -> bool { debug_assert!(l_index < self.len()); debug_assert!(r_index < self.len()); self.find(l_index) == self.find(r_index) } pub fn count_elements(&mut self, index: usize) -> usize { debug_assert!(index < self.len()); let root_index = self.find(index); match self.nodes[root_index] { Node::Root { node_count } => node_count, _ => unreachable!("`find` must return root index"), } } } } } pub mod io { pub use self::scanner::*; mod scanner { use std::io::BufRead; use std::marker::PhantomData; use std::str::{from_utf8, FromStr}; pub struct Scanner { reader: R, buffer: Vec, position: usize, } impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buffer: vec![], position: 0 } } pub fn next(&mut self) -> Option { Parse::parse(self.next_bytes().unwrap_or(&[])) } pub fn take(&mut self, n: usize) -> Take { Take { scanner: self, n: n, _marker: PhantomData } } pub fn next_bytes(&mut self) -> Option<&[u8]> { if self.buffer.is_empty() { self.read_line(); } loop { match self.buffer.get(self.position) { Some(&b' ') => self.position += 1, Some(&b'\n') => self.read_line(), Some(_) => break, None => return None, } } let start = self.position; loop { match self.buffer.get(self.position) { Some(&b' ') | Some(&b'\n') | None => break, Some(_) => self.position += 1, } } Some(&self.buffer[start..self.position]) } fn read_line(&mut self) { self.position = 0; self.buffer.clear(); self.reader.read_until(b'\n', &mut self.buffer).unwrap(); } } pub struct Take<'a, R: 'a, T> { scanner: &'a mut Scanner, n: usize, _marker: PhantomData T>, } impl<'a, R: BufRead, T: Parse> Iterator for Take<'a, R, T> { type Item = Option; fn next(&mut self) -> Option { if self.n > 0 { self.n -= 1; Some(self.scanner.next()) } else { None } } fn size_hint(&self) -> (usize, Option) { (self.n, Some(self.n)) } } impl<'a, R: BufRead, T: Parse> ExactSizeIterator for Take<'a, R, T> {} pub trait Parse: Sized { fn parse(bytes: &[u8]) -> Option; } impl Parse for u8 { fn parse(bytes: &[u8]) -> Option { if bytes.len() == 1 { Some(*unsafe { bytes.get_unchecked(0) }) } else { None } } } macro_rules! parse_impl { ($($t:ident)+) => {$( impl Parse for $t { fn parse(bytes: &[u8]) -> Option { from_utf8(bytes).ok().and_then(|s| $t::from_str(s).ok()) } } )+}; } parse_impl! { i32 i64 u32 u64 isize usize String } } }