#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) typedef long long ll; typedef uint64_t ull; typedef pair P; typedef pair Pid; typedef pair Pdi; typedef pair Pl; typedef pair> PP; typedef pair PPi; constexpr double PI = 3.1415926535897932; // acos(-1) constexpr double EPS = 1e-9; constexpr int INF = 1001001001; constexpr int mod = 1e+9 + 7; // constexpr int mod = 998244353; template struct LowLink{ const G& g; vector visited, order, low; vector articulation; // 関節点 vector> bridge; // 橋 (order[from] < low[to]) int LinkSize = 0; LowLink(const G &g) : g(g) {} int dfs(int from, int k, int par = -1){ visited[from] = true; order[from] = k++; low[from] = order[from]; bool is_articulation = false; int cnt = 0; for(auto &to : g[from]){ if(!visited[to]){ ++cnt; k = dfs(to, k, from); low[from] = min(low[from], low[to]); // 頂点 from がDFS木の根以外であるときの関節点となる条件 is_articulation |= ~par && low[to] >= order[from]; // (from, to) が条件を満たせば、橋に追加 if(order[from] < low[to]) bridge.emplace_back(minmax(from, (int)to)); } else if(to != par){ low[from] = min(low[from], order[to]); } } // 頂点 from がDFS木の根であるときの関節点となる条件 is_articulation |= par == -1 && cnt > 1; if(is_articulation) articulation.push_back(from); return k; } virtual void build(){ visited.assign(g.size(), 0); order.assign(g.size(), 0); low.assign(g.size(), 0); int k = 0; for(int i = 0; i < g.size(); ++i){ if(!visited[i]) k = dfs(i, k), ++LinkSize; } } }; using G = vector>; G graph; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; graph.resize(n); for(int i = 0; i < n - 1; ++i){ int u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } LowLink lowlink(graph); lowlink.build(); int LinkSize = lowlink.LinkSize; if(LinkSize == 1){ puts("Bob"); return 0; } if(LinkSize >= 3){ puts("Alice"); return 0; } int BridgeSize = lowlink.bridge.size(); if(BridgeSize == 0) puts("Bob"); else puts("Alice"); }