#ifndef CLASS_DISJOINT_SET #define CLASS_DISJOINT_SET #include #include #include class disjoint_set { private: typedef std::int32_t value_type; std::size_t n; std::vector val; public: disjoint_set() : n(0) {}; disjoint_set(std::size_t n_) : n(n_), val(std::vector(n_, value_type(-1))) {}; std::size_t size() const { return n; } std::size_t size(std::size_t elem) { return std::size_t(-val[root(elem)]); } std::size_t root(std::size_t elem) { // path halving while (val[elem] >= 0 && val[val[elem]] >= 0) { val[elem] = val[val[elem]]; elem = val[elem]; } return std::size_t(val[elem] >= 0 ? val[elem] : elem); } void link(std::size_t elemx, std::size_t elemy) { elemx = root(elemx); elemy = root(elemy); if (elemx == elemy) return; if (val[elemx] > val[elemy]) { std::swap(elemx, elemy); } val[elemx] += val[elemy]; val[elemy] = elemx; } bool connected(std::size_t elemx, std::size_t elemy) { return root(elemx) == root(elemy); } }; #endif // CLASS_DISJOINT_SET #include #include #include #include #include #include #include using namespace std; int main() { int N; cin >> N; disjoint_set uf(N); vector deg(N); for (int i = 0; i < N - 1; ++i) { int a, b; cin >> a >> b; uf.link(a, b); ++deg[a]; ++deg[b]; } set s; for (int i = 0; i < N; ++i) { s.insert(uf.root(i)); } sort(deg.begin(), deg.end()); vector tar(N, 2); tar[0] = 0; if (s.size() == 1 || (s.size() == 2 && tar == deg)) { cout << "Bob" << endl; } else { cout << "Alice" << endl; } return 0; }