#include #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; struct LowLink { vector used, ord, low, articulation; vector> bridge; LowLink(vector> &G) { int N = G.size(), id = 0; used.assign(N, 0); ord.assign(N, 0); low.assign(N, 0); for(int i = 0; i < N; i++) if(!used[i]) dfs(G, i, -1, id); } void dfs(vector> &G, int v, int p, int &id) { used[v] = 1; ord[v] = low[v] = id++; bool p_used = false, is_articulation = false; int cnt = 0; for(int to : G[v]) { if(to == p && !p_used) { p_used = true; continue; } if(!used[to]) { cnt++; dfs(G, to, v, id); low[v] = min(low[v], low[to]); if(p >= 0 && low[to] >= ord[v]) is_articulation = true; if(low[to] > ord[v]) bridge.push_back({v, to}); } else { low[v] = min(low[v], ord[to]); } } if(p == -1 && cnt >= 2) is_articulation = true; if(is_articulation) articulation.push_back(v); } }; class union_find { public: union_find(int n) : data(n, -1) {} int unite(int x, int y) { x = root(x), y = root(y); if(x != y) { if(size(x) < size(y)) swap(x, y); data[x] += data[y]; return data[y] = x; } return -1; } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } bool same(int x, int y) { return root(x) == root(y); } private: vector data; }; int main(){ cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; vector> G(N); union_find uf(N); vector d(N, 0); rep(i,N-1) { int u,v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); uf.unite(u, v); d[u]++, d[v]++; } set st; rep(i,N) st.insert(uf.root(i)); /* int ok1 = (LowLink(G).bridge.size() >= 1u) && (st.size() >= 2u); int ok2 = (st.size() >= 3); cout << (ok1 || ok2 ? "Alice" : "Bob") << endl; */ if(st.size() == 1u) { cout << "Bob" << endl; } else if(st.size() >= 3u) { cout << "Alice" << endl; } else { set set_d; for(int x : d) set_d.insert(x); cout << (set_d == set{0, 2} ? "Bob" : "Alice") << endl; } }