#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; struct UnionFind { private: vector par,ran; int n; public: vector edge,size; UnionFind(int x){ n=x; par.resize(n,0); ran.resize(n,0); edge.resize(n,0); size.resize(n,1); rep(i,n){ par[i]=i; } } int find(int x) { if (par[x]==x)return x; else return par[x]=find(par[x]); } void unite(int x, int y) { x=find(x),y=find(y); if (x==y){ edge[x]++; return; } if (ran[x] ord,low,par,blg,num; vector root; vector > G,C,T; vector > > E; vector ap; vector > bs,cand; LowLink(int n):n(n),pos(0),ord(n,-1),low(n),root(n), par(n,-1),blg(n,-1),num(n,1),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } bool is_joint(int u){ if (root[u]) return G[u].size()>=2; else{ for(int v:G[u]){ if(ord[u]<=low[v]){ return true; } } return false; } } bool is_bridge(int u,int v){ if(ord[u]>ord[v]) swap(u,v); return ord[u]=ord[v]){ E.emplace_back(); while(1){ auto e=cand.back(); cand.pop_back(); E.back().emplace_back(e); if(make_pair(min(u,v),max(u,v))==e) break; } } } } void fill_component(int v){ C[blg[v]].emplace_back(v); for(int u:G[v]){ if(~blg[u]||is_bridge(u,v)) continue; blg[u]=blg[v]; fill_component(u); } } void add_component(int v,int &k){ if(~blg[v]) return; blg[v]=k++; C.emplace_back(); fill_component(v); } int build(){ for(int i=0;i cnt(n,0); for(int i=0;i1) ap.emplace_back(i); sort(ap.begin(),ap.end()); ap.erase(unique(ap.begin(),ap.end()),ap.end()); int k=0; for(int i=0;i()); for(auto e:bs){ int u=blg[e.first],v=blg[e.second]; T[u].emplace_back(v); T[v].emplace_back(u); } return k; } }; int n; P E[100010]; void solve(){ cin >> n; LowLink low(n);UnionFind uf(n); rep(i,n-1){ int u,v; cin >> u >> v; E[i]=P(u,v); low.add_edge(u,v); uf.unite(u,v); } low.build(); set S{}; rep(i,n){ S.insert(uf.find(i)); } int size=S.size(); //cout << size << endl; if (size==1) cout << "Bob" << endl; if (size>=3) cout << "Alice" << endl; if (size==2){ rep(i,n-1){ //cout << E[i].first << " " << E[i].second << " " << low.is_bridge(E[i].first,E[i].second) << endl; if (low.is_bridge(E[i].first,E[i].second)) { cout << "Alice" << endl; return; } } cout << "Bob" << endl; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }