#![allow(unused)] use kyoproio::*; use std::{ collections::*, iter, io::{self, prelude::*}, mem::{replace, swap}, }; fn main() -> io::Result<()> { std::thread::Builder::new() .stack_size(50 * 1024 * 1024) .spawn(solve)? .join() .unwrap(); Ok(()) } fn solve() { let stdin = io::stdin(); let mut kin = Input::new(stdin.lock()); let stdout = io::stdout(); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+) }; } let n: usize = kin.input(); let mut g: Vec<_> = iter::repeat_with(|| Vec::new()).take(n + 1).collect(); for _ in 0..n - 1 { let (u, v): (usize, usize) = kin.input(); g[u].push(v); g[v].push(u); } let ans = (|| { let size = dfs_size(&g, &mut vec![false; n], 0).max(dfs_size(&g, &mut vec![false; n], 1)); eprintln!("size: {}", size); if size == n { return false; } if size == n - 1 { let mut d0 = 0; let mut d2 = 0; for u in 0..n { d0 += (g[u].len() == 0) as usize; d2 += (g[u].len() == 2) as usize; } return if d0 == 1 && d2 == n - 1 { false } else { true } } true })(); output!("{}\n", ["Bob", "Alice"][ans as usize]); } fn dfs_size(g: &[Vec], vis: &mut [bool], u: usize) -> usize { if vis[u] { return 0; } vis[u] = true; let mut s = 1; for &v in g[u].iter() { s += dfs_size(g, vis, v); } s } // -------------------------------------------------------------------------------- pub mod kyoproio { pub use std::io::prelude::*; pub struct Input { src: R, buf: String, pos: usize, } impl Input { pub fn new(src: R) -> Self { Self { src, buf: String::with_capacity(256), pos: 0, } } pub fn raw(&mut self) -> &str { loop { if self.pos >= self.buf.len() { self.buf.clear(); let len = self.src.read_line(&mut self.buf).expect("io error"); self.pos = 0; } let range = self.pos ..self.buf[self.pos..] .find(|c: char| c.is_ascii_whitespace()) .map(|i| i + self.pos) .unwrap_or(self.buf.len()); self.pos = range.end + 1; if range.end - range.start > 0 { return &self.buf[range]; } } } pub fn input(&mut self) -> T { self.input_fallible().expect("input error") } pub fn input_fallible(&mut self) -> Result { T::input(self) } pub fn iter(&mut self) -> Iter { Iter { input: self, _t: std::marker::PhantomData, } } } pub struct Iter<'a, T, R> { input: &'a mut Input, _t: std::marker::PhantomData, } impl<'a, T: InputParse, R: BufRead> Iterator for Iter<'a, T, R> { type Item = T; fn next(&mut self) -> Option { Some(self.input.input()) } } type Result = std::result::Result>; pub trait InputParse: Sized { fn input(input: &mut Input) -> Result; } macro_rules! input_from_str_impls { { $($T:ty)* } => { $(impl InputParse for $T { fn input(input: &mut Input) -> Result { input.raw().parse::<$T>().map_err(|e| e.into()) } })* }; } macro_rules! input_tuple_impls { { $(($($T:ident),+))* } => { $(impl<$($T:InputParse),+> InputParse for ($($T),+) { fn input(input: &mut Input) -> Result { Ok( ($(match $T::input(input) { Ok(v) => v, Err(e) => return Err(e) }),+) ) } })* }; } input_from_str_impls! { String char bool f32 f64 isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128 } input_tuple_impls! { (A, B) (A, B, C) (A, B, C, D) (A, B, C, D, E) (A, B, C, D, E, F) (A, B, C, D, E, F, G) } }