#![allow(unused_macros)] macro_rules! rep { ($n: expr, $body: block) => { for _ in 0..$n { $body } }; ($i: ident, $n: expr, $body: block) => { for $i in 0..$n { $body } }; ($i: ident, $a: expr, $b: expr, $body: block) => { for $i in $a..=$b { $body } }; ($i: ident, $a: expr, $b: expr, $c: expr, $body: block) => { let mut $i = $a; while $i <= $b { $body $i += $c; } }; } macro_rules! rvp { ($i: ident, $n: expr, $body: block) => { for $i in (0..$n).rev() { $body } }; ($i: ident, $a: expr, $b: expr, $body: block) => { for $i in ($b..=$a).rev() { $body } }; ($i: ident, $a: expr, $b: expr, $c: expr, $body: block) => { let mut $i = $a; while $i >= $b { $body $i -= $c; } }; } macro_rules! each { ($el: ident, $v: expr, $body: block) => { for $el in $v { $body } } } #[allow(dead_code)] fn out(x: T) { print!("{}", x); } macro_rules! out { () => { println!(); }; ($head:expr $(, $tail:expr)*) => { out($head); $( print!(" "); out($tail); )* println!(); }; } #[allow(dead_code)] const MOD: i32 = 998244353; #[allow(dead_code)] const M0D: i32 = 1e9 as i32 + 7; #[allow(dead_code)] const INF: i32 = 1 << 30; #[allow(dead_code)] const LINF: i64 = (1 << 61) - 1; #[allow(dead_code)] #[allow(non_upper_case_globals)] const dx: [i32; 9] = [0, -1, 1, 0, 0, -1, -1, 1, 1]; #[allow(dead_code)] #[allow(non_upper_case_globals)] const dy: [i32; 9] = [0, 0, 0, -1, 1, -1, 1, -1, 1]; const MULTI: bool = false; pub fn main() { rep!(match MULTI { true => { let mut num = String::new(); std::io::stdin().read_line(&mut num).expect("invalid input"); num.parse().unwrap() } _ => 1 }, { solve(); }); } fn solve() { proconio::input!{n: usize} let mut uf = UnionFind::new(n); let mut gg = true; let mut cnt = vec![0; n]; for _ in 0..n - 1 { proconio::input! { u: usize, v: usize } gg &= uf.unite(u, v); cnt[u] += 1; cnt[v] += 1; } if gg { return println!("Bob"); } if cnt.iter().any(|&e| e >= 1 && e != 2) { return println!("Alice"); } out!(match uf.size(0) == n - 1 || uf.size(1) == n - 1 { true => "Bob", _ => "Alice" }); } pub trait DSU { fn new(n: usize) -> Self; fn root(&mut self, i: usize) -> usize; fn size(&mut self, i: usize) -> usize; fn unite(&mut self, i: usize, j: usize) -> bool; fn same(&mut self, i: usize, j: usize) -> bool { self.root(i) == self.root(j) } fn groups(&mut self) -> Vec>; } pub struct UnionFind { par: Vec } impl DSU for UnionFind { fn new(n: usize) -> Self { Self { par: vec![-1; n] } } fn root(&mut self, i: usize) -> usize { if self.par[i] >= 0 { self.par[i] = self.root(self.par[i] as usize) as i32; self.par[i] as usize } else { i } } fn size(&mut self, i: usize) -> usize { let id = self.root(i); -self.par[id] as usize as usize } fn unite(&mut self, mut i: usize, mut j: usize) -> bool { i = self.root(i); j = self.root(j); if i == j { return false; } if i > j { std::mem::swap(&mut i, &mut j); } self.par[i] += self.par[j]; self.par[j] = i as i32; true } fn groups(&mut self) -> Vec> { let n = self.par.len(); let mut res = vec![Vec::new(); n]; for i in 0..n { res[self.root(i)].push(i); } res.into_iter().filter(|g| !g.is_empty()).collect() } } pub fn is_bipartite(mut uf: UnionFind) -> bool { assert_eq!(uf.par.len() % 2, 0); let n = uf.par.len() / 2; let mut ok = true; for i in 0..n { ok &= uf.root(i) != uf.root(i + n); } ok }