#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; template using posteriority_queue = priority_queue, greater >; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } template void unique(vector &a) { a.erase(unique(ALL(a)), a.end()); } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; struct UnionFind { UnionFind(int n) : data(n, -1) {} int root(int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (data[u] > data[v]) swap(u, v); data[u] += data[v]; data[v] = u; return true; } bool same(int u, int v) { return root(u) == root(v); } int size(int ver) { return -data[root(ver)]; } private: vector data; }; using CostType = ll; struct Edge { int src, dst; CostType cost; Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {} inline bool operator<(const Edge &rhs) const { return cost != rhs.cost ? cost < rhs.cost : dst != rhs.dst ? dst < rhs.dst : src < rhs.src; } inline bool operator<=(const Edge &rhs) const { return !(rhs < *this); } inline bool operator>(const Edge &rhs) const { return rhs < *this; } inline bool operator>=(const Edge &rhs) const { return !(*this < rhs); } }; vector detect_bridge(const vector > &graph, bool heavy = false) { int n = graph.size(); vector res; vector depth(n, -1), imos(n, 0); function dfs = [&](int par, int ver) { bool multiedge = false; for (const Edge &e : graph[ver]) { if (depth[e.dst] == -1) { depth[e.dst] = depth[ver] + 1; dfs(ver, e.dst); if (imos[e.dst] == 0) res.emplace_back(min(ver, e.dst), max(ver, e.dst), e.cost); imos[ver] += imos[e.dst]; } else if (!multiedge && e.dst == par) { multiedge = true; } else if (depth[e.dst] < depth[ver]) { ++imos[ver]; --imos[e.dst]; } } }; REP(i, n) { if (depth[i] == -1) { depth[i] = 0; dfs(-1, i); } } if (heavy) { sort(ALL(res), [](const Edge &lhs, const Edge &rhs) { return lhs.src != rhs.src ? lhs.src < rhs.src : lhs.dst != rhs.dst ? lhs.dst < rhs.dst : lhs.cost < rhs.cost; }); } return res; } int main() { int n; cin >> n; UnionFind uf(n); vector > graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; graph[u].emplace_back(u, v); graph[v].emplace_back(v, u); uf.unite(u, v); } if (uf.size(0) == n) { cout << "Bob\n"; return 0; } set st; REP(i, n) st.emplace(uf.root(i)); if (st.size() >= 3) { cout << "Alice\n"; return 0; } cout << (detect_bridge(graph).empty() ? "Bob\n" : "Alice\n"); return 0; }