#include using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; #define rep(i,n) for(ll i=0;i T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); } template T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); } template inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template ostream &operator<<(ostream &os, const vector &a){ if (a.empty()) return os; os << a.front(); for (auto e : a | views::drop(1)){ os << ' ' << e; } return os; } void dump(auto ...vs){ ((cout << vs << ' '), ...) << endl; } namespace noya2 { template struct binary_trie { struct node { node *p; array ch; int leaf, sz; node () : p(nullptr), ch({nullptr,nullptr}), leaf(0), sz(0) {} }; binary_trie () : lazy(0) {} int size(node *v){ if (v == nullptr) return 0; return v->sz; } int size(){ return size(root); } void insert(T x){ x ^= lazy; node *v = root; for (int i = LOG-1; i >= 0; i--){ int j = x >> i & 1; if (v->ch[j] == nullptr){ v->ch[j] = new node(); v->ch[j]->p = v; } v = v->ch[j]; } v->leaf = 1; update(v); for (int i = 0; i < LOG; i++){ v = v->p; update(v); } } void erase(T x){ x ^= lazy; node *v = root; for (int i = LOG-1; i >= 0; i--){ int j = x >> i & 1; if (v->ch[j] == nullptr) return ; v = v->ch[j]; } v->leaf = 0; update(v); for (int i = 0; i < LOG; i++){ node *p = v->p; if (size(v) == 0){ (v == p->ch[0] ? p->ch[0] : p->ch[1]) = nullptr; delete v; } v = p; update(v); } } int count(T x){ node *v = root; int res = 0; for (int i = LOG-1; i >= 0; i--){ int j = lazy >> i & 1; if (x >> i & 1){ res += size(v->ch[j]); v = v->ch[j^1]; } else { v = v->ch[j]; } if (v == nullptr) break; } return res; } T get(int k){ if (k < 0 || k >= size()) return -1; node *v = root; T ans = 0; for (int i = LOG-1; i >= 0; i--){ int j = lazy >> i & 1; if (k < size(v->ch[j])){ v = v->ch[j]; } else { k -= size(v->ch[j]); v = v->ch[j^1]; ans |= T(1) << i; } } return ans; } T mex(){ if ((T)size() == (T(1)<= 0; i--){ int j = lazy >> i & 1; if ((T)size(v->ch[j]) < (T(1)<ch[j]; } else { v = v->ch[j^1]; ans |= T(1) << i; } if (v == nullptr) break; } return ans; } T xor_all(T x){ return lazy ^= x; } vector enumerate(){ vector ans; ans.reserve(size()); auto dfs = [&](auto sfs, int i, T x, node *v) -> void { if (i == -1){ ans.emplace_back(x^lazy); return ; } if (v->ch[0] != nullptr){ sfs(sfs,i-1,x,v->ch[0]); } if (v->ch[1] != nullptr){ sfs(sfs,i-1,x|(T(1)<ch[1]); } }; dfs(dfs,LOG-1,0,root); return ans; } private: T lazy; node *root = new node(); void update(node *v){ v->sz = v->leaf + size(v->ch[0]) + size(v->ch[1]); } }; } // namespace noya2 using namespace noya2; void solve() { ll N; cin>>N; // assert(N<5000); vector> edge(N); rep(i,N-1){ ll a,b; cin>>a>>b; a--; b--; edge[a].push_back(b); edge[b].push_back(a); } vector sz(N); vector heavy(N); { auto dfs=[&](auto self,ll cp,ll bp)->ll { ll v=1; ll hc=-1; ll hs=-1; for (ll np:edge[cp]){ if (np==bp)continue; ll res=self(self,np,cp); v+=res; if (chmax(hs,res)){ hc=np; } } sz[cp]=v; heavy[cp]=hc; return v; }; dfs(dfs,0,-1); } vector G(N); using bt = binary_trie; vector bl; bl.reserve(N+10); { auto dfs=[&](auto self,ll cp,ll bp)->int { if (sz[cp]==1){ G[cp]=1; bt b; b.insert(0); int idx=bl.size(); bl.emplace_back(b); return idx; } ll hp=heavy[cp]; bt &b=bl[self(self,hp,cp)]; b.insert(G[hp]); ll ax=G[hp]; for (ll np:edge[cp]){ if (np==bp or np==hp)continue; self(self,np,cp); ax^=G[np]; } b.xor_all(ax^G[hp]); ll now=ax; auto dfs2=[&](auto self,ll cp,ll bp)->void { ll v=0; v^=G[cp]; for (ll np:edge[cp]){ if (np==bp)continue; v^=G[np]; } now^=v; b.insert(now); for (ll np:edge[cp]){ if (np==bp)continue; self(self,np,cp); } now^=v; return; }; for (ll np:edge[cp]){ if (np==bp or np==hp)continue; dfs2(dfs2,np,cp); } G[cp]=b.mex(); int idx=bl.size(); bl.emplace_back(b); return idx; }; dfs(dfs,0,-1); } // dump(G); vector W; { ll now=0; auto dfs=[&](auto self,ll cp,ll bp)->void { for (ll np:edge[cp]){ if (np==bp)continue; now^=G[np]; } if (now==0){ W.push_back(cp); } // dump(cp,now); for (ll np:edge[cp]){ if (np==bp)continue; now^=G[np]; self(self,np,cp); now^=G[np]; } for (ll np:edge[cp]){ if (np==bp)continue; now^=G[np]; } return; }; dfs(dfs,0,-1); } cout<<"Alice"<<'\n'; cout<sync_with_stdio(0); ll T=1; while (T--){ solve(); } return 0; }