#include #include #include using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 vector> gs; vector>> vs; vector> E; int G[200005]; void dfs(int cv,int pv){ vector nxt; int X = 0; rep(i,E[cv].size()){ int to = E[cv][i]; if(to==pv)continue; dfs(to,cv); nxt.push_back(to); X ^= G[to]; } vector ngs; rep(i,nxt.size()){ rep(j,gs[nxt[i]].size()){ gs[nxt[i]][j] ^= X ^ G[nxt[i]]; ngs.push_back(gs[nxt[i]][j]); } } ngs.push_back(X); sort(ngs.begin(),ngs.end()); ngs.erase(unique(ngs.begin(),ngs.end()),ngs.end()); gs[cv] = ngs; vs[cv].resize(ngs.size()); rep(i,nxt.size()){ rep(j,gs[nxt[i]].size()){ int d = lower_bound(ngs.begin(),ngs.end(),gs[nxt[i]][j])-ngs.begin(); if(vs[cv][d].size() < vs[nxt[i]][j].size()){ swap(vs[cv][d],vs[nxt[i]][j]); } while(vs[nxt[i]][j].size()){ int v = vs[nxt[i]][j].back(); vs[nxt[i]][j].pop_back(); vs[cv][d].push_back(v); } } gs[nxt[i]].clear(); vs[nxt[i]].clear(); } rep(i,ngs.size()){ if(ngs[i]==X){ vs[cv][i].push_back(cv); } } rep(i,1000000){ if(i>=ngs.size() || ngs[i]!=i){ G[cv] = i; break; } } } int main(){ int n; cin>>n; gs.resize(n); vs.resize(n); E.resize(n); rep(i,n-1){ int a,b; cin>>a>>b; a--,b--; E[a].push_back(b); E[b].push_back(a); } dfs(0,-1); sort(vs[0][0].begin(),vs[0][0].end()); cout<<"Alice"<