fn main() { let n: usize = io::input(); let mut g = vec![vec![]; n]; for _ in 0..n - 1 { let (u, v): (usize, usize) = io::input(); let (u, v) = (u - 1, v - 1); g[u].push(v); g[v].push(u); } let mut stack = vec![0]; let mut ord = Vec::new(); let mut parent = vec![usize::MAX; n]; while let Some(x) = stack.pop() { ord.push(x); for &y in &g[x] { if y == parent[x] { continue; } parent[y] = x; stack.push(y); } } let mut dp = vec![(0, 0); n]; for &x in ord.iter().rev() { for &y in &g[x] { if y == parent[x] { continue; } dp[x].0 += dp[y].1; dp[x].1 += dp[y].0.max(dp[y].1); } dp[x].0 += 1; } let ans = dp[0].0.max(dp[0].1); println!("{}", ans); } // io {{{ // https://ngtkana.github.io/ac-adapter-rs/io/index.html #[allow(dead_code)] mod io { use std::cell::Cell; use std::io::stdin; use std::io::BufRead; use std::io::BufReader; use std::io::Lines; use std::io::Stdin; use std::sync::Mutex; use std::sync::Once; pub fn input() -> T { ParseLine::parse_line(&line()) } pub trait ParseLine { fn parse_line(s: &str) -> Self; } macro_rules! impl_parse_line { ($($t:ty),*) => { $(impl ParseLine for $t { fn parse_line(s: &str) -> Self { s.parse().unwrap() } })* }; } impl_parse_line!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, String, char); macro_rules! impl_parse_line_tuple { ($($t:ident),*) => { impl<$($t: ParseLine),*> ParseLine for ($($t,)*) { fn parse_line(s: &str) -> Self { let mut s = s.split_whitespace(); ($($t::parse_line(s.next().unwrap()),)*) } } }; } impl_parse_line_tuple!(T0, T1); impl_parse_line_tuple!(T0, T1, T2); impl_parse_line_tuple!(T0, T1, T2, T3); impl_parse_line_tuple!(T0, T1, T2, T3, T4); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9); impl ParseLine for Vec { fn parse_line(s: &str) -> Self { s.split_whitespace().map(T::parse_line).collect() } } static ONCE: Once = Once::new(); type Server = Mutex>>; struct Lazy(Cell>); unsafe impl Sync for Lazy {} fn line() -> String { static SYNCER: Lazy = Lazy(Cell::new(None)); ONCE.call_once(|| { SYNCER .0 .set(Some(Mutex::new(BufReader::new(stdin()).lines()))); }); unsafe { (*SYNCER.0.as_ptr()) .as_ref() .unwrap() .lock() .unwrap() .next() .unwrap() .unwrap() } } } // }}}