#include #define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++) #define rep(i, begin, end) for(int i = int(begin); i < int(end); i++) #define all(v) v.begin(), v.end() void alice() { std::cout << "Alice" << std::endl; exit(0); } void bob() { std::cout << "Bob" << std::endl; exit(0); } int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); int n; std::cin >> n; std::vector< std::vector< int > > graph(n); loop(n - 1) { int u, v; std::cin >> u >> v; graph.at(u).emplace_back(v); graph.at(v).emplace_back(u); } auto root = -1; rep(i, 0, n) { if (!graph.at(i).empty()) { root = i; } } std::vector< int > ckd(n, false); std::queue< int > que; que.emplace(root); while(!que.empty()) { auto crr = que.front(); que.pop(); for (auto nxt : graph.at(crr)) { if (ckd.at(nxt)) continue; ckd.at(nxt) = true; que.emplace(nxt); } } auto cmp = std::accumulate(all(ckd), 0); if (cmp == n) bob(); if (cmp <= n - 2) alice(); for (auto const & v : graph) { if (!v.empty() && v.size() != 2u) alice(); } bob(); return 0; }