//include //------------------------------------------ #include #include #include #include #include #include #include #include #include #include #include #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; // typedef //------------------------------------------ typedef long long LL; typedef vector VI; typedef vector VB; typedef vector VC; typedef vector VD; typedef vector VS; typedef vector VLL; typedef vector VVI; typedef vector VVB; typedef vector VVS; typedef vector VVLL; typedef vector VVVI; typedef vector VVVLL; typedef pair PII; typedef pair PLL; typedef pair PIS; typedef pair PSI; typedef pair PSS; typedef vector VPII; typedef vector VPLL; typedef vector VVPII; typedef vector VVPLL; typedef vector VVS; typedef map MII; typedef map MLL; typedef map MSI; typedef map MIS; // container util //------------------------------------------ #define ALL(a) (a).begin(),(a).end() #define SZ(a) int((a).size()) #define EACH(i, arr) for(typeof((arr).begin()) i=(arr).begin(); i!=(arr).end(); ++i) #define EXIST(str, e) ((str).find(e)!=(str).end()) #define COUNT(arr, v) count((arr).begin(), (arr).end(), v) #define SEARCH(v, w) search((v).begin(), (v).end(), (w).begin(), (w).end()) #define SORT(c) sort((c).begin(),(c).end()) #define RSORT(c) sort((c).rbegin(),(c).rend()) #define REVERSE(c) reverse((c).begin(), (c).end()) #define ROTATE_LEFT(arr, c) rotate((arr).begin(), (arr).begin()+(c), (arr).end()) #define ROTATE_RIGHT(arr, c) rotate((arr).rbegin(), (arr).rbegin() + (c), (arr).rend()) #define SUMI(arr) accumulate((arr).begin(), (arr).end(), 0) #define SUMD(arr) accumulate((arr).begin(), (arr).end(), 0.) #define SUMLL(arr) accumulate((arr).begin(), (arr).end(), 0LL) #define MULD(arr) accumulate((arr).begin(), (arr).end(), 1., multiplies()) #define UB(arr, n) upper_bound((arr).begin(), (arr).end(), n) #define LB(arr, n) lower_bound((arr).begin(), (arr).end(), n) #define PB push_back #define MP make_pair #define ft first #define sd second // input output //------------------------------------------ #define GL(s) getline(cin, (s)) #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0) #define OUT(d) std::cout<<(d) #define OUT_L(d) std::cout<<(d)< istream &operator>>(istream &in, pair &p) { in >> p.first >> p.second; return in; } template istream &operator>>(istream &in, vector &v) { for (auto &x: v) in >> x; return in; } template ostream &operator<<(ostream &out, const std::pair &p) { out << "[" << p.first << ", " << p.second << "]" << "\n"; return out; } //repetition //------------------------------------------ #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i) #define REP(i, n) FOR(i,0,n) #define RREP(i, n) for(int i = n-1;i >= 0;i--) #define FORLL(i, a, b) for(LL i=LL(a);i=LL(a);--i) #define REPLL(i, n) for(LL i=0;i=0;--i) #define FOREACH(x, arr) for(auto &(x) : (arr)) //------------------------------------------ //------------------------------------------ struct UnionFind { vector par; vector sizes; UnionFind(int n) : par(n), sizes(n, 1) { for (int i = 0; i < n; i++) { par[i] = i; } } int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sizes[x] < sizes[y]) swap(x, y); par[y] = x; sizes[x] += sizes[y]; } bool same(int x, int y) { return find(x) == find(y); } int get_size(int x) { return sizes[find(x)]; } bool all_same() { bool good = true; for (int i = 0, n = par.size(); i < n; i++) if (find(0) != find(i)) good = false; return good; } int get_connectivity() { set s; for (int i = 0, n = par.size(); i < n; i++) s.insert(find(i)); return s.size(); } }; template struct Edge { int from, to; T cost; Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} explicit operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnWeightedGraph = vector>; template using DistMatrix = vector>; struct GraphAdapter { template static UnWeightedGraph to_unweighted_graph(const WeightedGraph &origin) { int V = origin.size(); UnWeightedGraph graph(V); for (int i = 0; i < V; i++) for (auto &e: origin[i]) graph[i].push_back((int) e); return graph; } static WeightedGraph to_weighted_graph(const UnWeightedGraph &origin) { int V = origin.size(); WeightedGraph graph(V); for (int i = 0; i < V; i++) for (auto to: origin[i]) graph[i].push_back({i, to, 1}); return graph; } template static DistMatrix to_dist_matrix(const WeightedGraph &origin, T INF) { int V = origin.size(); DistMatrix matrix(V, vector(V, INF)); for (int i = 0; i < V; i++) for (auto &e:origin[i]) matrix[i][e.to] = e.cost; for (int i = 0; i < V; i++) matrix[i][i] = 0; return matrix; } }; template struct LowLink { const G &g; int k; vector used, ord, low; vector articulations; vector> bridges; LowLink(const G &g) : g(g) {} void dfs(int v, int p) { used[v] = 1; ord[v] = low[v] = k++; bool is_art = false; int cnt = 0; for (auto &to: g[v]) { if (!used[to]) { cnt++; dfs(to, v); low[v] = min(low[v], low[to]); is_art |= ~p && ord[v] <= low[to]; if (ord[v] < low[to]) bridges.emplace_back(min(v, (int) to), max(v, (int) to)); } else if (to != p) { low[v] = min(low[v], ord[v]); } } is_art |= p == -1 and cnt > 1; if (is_art) articulations.push_back(v); } void build() { int n = g.size(); used.assign(n, 0); ord.assign(n, 0); low.assign(n, 0); k = 0; for (int i = 0; i < n; i++) { if (!used[i]) { dfs(i, -1); } } } }; int main() { int N; cin >> N; UnWeightedGraph G(N); UnionFind UF(N); REP(i, N - 1) { int a, b; cin >> a >> b; UF.unite(a, b); G[a].push_back(b); G[b].push_back(a); } int connects = UF.get_connectivity(); if (connects == 1) { cout << "Bob" << endl; return 0; } if (connects >= 3) { cout << "Alice" << endl; return 0; } LowLink lowLink(G); lowLink.build(); auto bridges = lowLink.bridges; if (bridges.size()) cout << "Alice" << endl; else cout << "Bob" << endl; }