#include #define mp make_pair #define pb push_back using namespace std; using ll = long long int; template ostream& operator+(ostream& out, const vector &vec){ for(const auto &x : vec){ out< ostream& operator*(ostream& out, const vector &vec){ for(const auto &x : vec){ out+x; } return out; } template istream& operator>>(istream& in, vector &vec){ for(auto &x : vec){ in>>x; } return in; } struct my_set{ int offset = 0; set s; auto view(){ return s | views::transform([&](int x){ return x ^ offset; }); } void add(int elem){ s.insert(elem ^ offset); } void add_offset(int more_offset){ offset ^= more_offset; } bool has(int elem){ return s.count(elem ^ offset); } int size() const { return s.size(); } void add_set(my_set &other){ if(other.size() > size()) swap(*this, other); for(int x : other.view()) add(x); } }; void solve(){ int n; cin>>n; vector> t(n); for(int i=1;i>u>>v; --u; --v; t[u].push_back(v); t[v].push_back(u); } vector grundy_vals(n); vector grundy(n); vector sub(n); auto dfs = [&](int u, int p, auto&& dfs) -> void { int ch = 0; int grundy_xor = 0; for(int v : t[u]){ if(v == p) continue; dfs(v, u, dfs); grundy_xor ^= grundy[v]; sub[u] += sub[v]; ch++; } if(ch == 0){ grundy_vals[u].add(0); grundy[u] = 1; return; } sort(t[u].begin(), t[u].end(), [&](int a, int b){ return grundy_vals[a].size() > grundy_vals[b].size(); }); for(auto &v : t[u]){ if(v == p) continue; grundy_vals[v].add_offset(grundy_xor ^ grundy[v]); grundy_vals[u].add_set(grundy_vals[v]); } sort(t[u].begin(), t[u].end(), [&](int a, int b){ return sub[a] > sub[b]; }); if(ch == 1){ grundy_vals[u].add(grundy[t[u][0]]); grundy[u] = grundy[t[u][0]] + 1; return; } int max_mex_diff = 1; while(max_mex_diff <= sub[t[u][1]]) max_mex_diff <<= 1; max_mex_diff *= 2; grundy_vals[u].add(grundy_xor); int mex = max(0, grundy[t[u][0]] - max_mex_diff); while(grundy_vals[u].has(mex)) mex++; grundy[u] = mex; }; dfs(0, -1, dfs); vector res; auto dfs2 = [&](int u, int p, int c_xor, auto&& dfs) -> void { int grundy_xor = 0; for(int v : t[u]){ if(v == p) continue; grundy_xor ^= grundy[v]; } if((grundy_xor ^ c_xor) == 0){ res.push_back(u + 1); } for(int v : t[u]){ if(v == p) continue; dfs(v, u, grundy_xor ^ c_xor ^ grundy[v], dfs); } }; dfs2(0, -1, 0, dfs2); if(res.size() == 0){ cout<<"Bob\n"; return; } cout<<"Alice\n"; cout<