#line 1 "a.cpp" #define PROBLEM "" #line 2 "/home/kuhaku/atcoder/github/algo/lib/template/template.hpp" #pragma GCC target("sse4.2,avx2,bmi2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include template bool chmax(T &a, const U &b) { return a < (T)b ? a = (T)b, true : false; } template bool chmin(T &a, const U &b) { return (T)b < a ? a = (T)b, true : false; } constexpr std::int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr int MOD = 1000000007; constexpr int MOD_N = 998244353; constexpr double EPS = 1e-7; constexpr double PI = M_PI; #line 3 "/home/kuhaku/atcoder/github/algo/lib/graph/graph.hpp" /** * @brief 重み付きグラフ * * @tparam T 辺の重みの型 */ template struct Graph { private: struct _edge { constexpr _edge() : _from(), _to(), _weight() {} constexpr _edge(int from, int to, T weight) : _from(from), _to(to), _weight(weight) {} constexpr bool operator<(const _edge &rhs) const { return this->weight() < rhs.weight(); } constexpr bool operator>(const _edge &rhs) const { return rhs < *this; } constexpr int from() const { return this->_from; } constexpr int to() const { return this->_to; } constexpr T weight() const { return this->_weight; } private: int _from, _to; T _weight; }; public: using edge_type = typename Graph::_edge; Graph() : _size(), edges() {} Graph(int v) : _size(v), edges(v) {} const auto &operator[](int i) const { return this->edges[i]; } auto &operator[](int i) { return this->edges[i]; } const auto begin() const { return this->edges.begin(); } auto begin() { return this->edges.begin(); } const auto end() const { return this->edges.end(); } auto end() { return this->edges.end(); } constexpr int size() const { return this->_size; } void add_edge(const edge_type &e) { this->edges[e.from()].emplace_back(e); } void add_edge(int from, int to, T weight = T(1)) { this->edges[from].emplace_back(from, to, weight); } void add_edges(int from, int to, T weight = T(1)) { this->edges[from].emplace_back(from, to, weight); this->edges[to].emplace_back(to, from, weight); } void input_edge(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; T weight; std::cin >> from >> to >> weight; this->add_edge(from - base, to - base, weight); } } void input_edges(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; T weight; std::cin >> from >> to >> weight; this->add_edges(from - base, to - base, weight); } } private: int _size; std::vector> edges; }; template <> struct Graph { private: struct _edge { constexpr _edge() : _from(), _to() {} constexpr _edge(int from, int to) : _from(from), _to(to) {} constexpr int from() const { return this->_from; } constexpr int to() const { return this->_to; } constexpr int weight() const { return 1; } constexpr bool operator<(const _edge &rhs) const { return this->weight() < rhs.weight(); } constexpr bool operator>(const _edge &rhs) const { return rhs < *this; } private: int _from, _to; }; public: using edge_type = typename Graph::_edge; Graph() : _size(), edges() {} Graph(int v) : _size(v), edges(v) {} const auto &operator[](int i) const { return this->edges[i]; } auto &operator[](int i) { return this->edges[i]; } const auto begin() const { return this->edges.begin(); } auto begin() { return this->edges.begin(); } const auto end() const { return this->edges.end(); } auto end() { return this->edges.end(); } constexpr int size() const { return this->_size; } void add_edge(const edge_type &e) { this->edges[e.from()].emplace_back(e); } void add_edge(int from, int to) { this->edges[from].emplace_back(from, to); } void add_edges(int from, int to) { this->edges[from].emplace_back(from, to); this->edges[to].emplace_back(to, from); } void input_edge(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; this->add_edge(from - base, to - base); } } void input_edges(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; this->add_edges(from - base, to - base); } } private: int _size; std::vector> edges; }; #line 3 "/home/kuhaku/atcoder/github/algo/lib/graph/lowlink.hpp" /** * @brief LowLink * * @tparam T */ template struct LowLink { LowLink(const Graph &_graph) : g(_graph), ord(_graph.size()), low(_graph.size()), used(_graph.size()) { this->build(); } /** * @brief Get the articulation points object * * @return std::vector */ auto get_articulation_points() { return this->articulation_points; } /** * @brief Get the bridges object * * @return std::vector::edge_type> */ auto get_bridges() { return this->bridges; } private: const Graph &g; std::vector ord, low; std::vector used; std::vector articulation_points; // 関節点 std::vector::edge_type> bridges; // 橋 void build() { int number = 0; for (int i = 0; i < this->g.size(); i++) { if (!this->used[i]) number = this->dfs(i, number, -1); } } int dfs(int index, int number, int parent) { this->used[index] = true; this->ord[index] = number++; this->low[index] = this->ord[index]; bool is_articulation_point = false; int count = 0; for (auto &e : this->g[index]) { if (!this->used[e.to()]) { ++count; number = this->dfs(e.to(), number, index); chmin(low[index], low[e.to()]); is_articulation_point |= ~parent && this->low[e.to()] >= this->ord[index]; if (this->ord[index] < this->low[e.to()]) this->bridges.emplace_back(e); } else if (e.to() != parent) { chmin(this->low[index], this->ord[e.to()]); } } is_articulation_point |= parent == -1 && count > 1; if (is_articulation_point) this->articulation_points.emplace_back(index); return number; } }; #line 3 "/home/kuhaku/atcoder/github/algo/lib/template/macro.hpp" #define FOR(i, m, n) for (int i = (m); i < int(n); ++i) #define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i) #define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i) #define rep(i, n) FOR (i, 0, n) #define repn(i, n) FOR (i, 1, n + 1) #define repr(i, n) FORR (i, n, 0) #define repnr(i, n) FORR (i, n + 1, 1) #define all(s) (s).begin(), (s).end() #line 3 "/home/kuhaku/atcoder/github/algo/lib/template/sonic.hpp" struct Sonic { Sonic() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } constexpr void operator()() const {} } sonic; #line 5 "/home/kuhaku/atcoder/github/algo/lib/template/atcoder.hpp" using namespace std; using ll = std::int64_t; using ld = long double; template std::istream &operator>>(std::istream &is, std::pair &p) { return is >> p.first >> p.second; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &i : v) is >> i; return is; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { return os << '(' << p.first << ',' << p.second << ')'; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (auto it = v.begin(); it != v.end(); ++it) { os << (it == v.begin() ? "" : " ") << *it; } return os; } template void co(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cout << head << '\n'; else std::cout << head << ' ', co(std::forward(tail)...); } template void ce(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n'; else std::cerr << head << ' ', ce(std::forward(tail)...); } template auto make_vector(T x, int arg, Args... args) { if constexpr (sizeof...(args) == 0) return std::vector(arg, x); else return std::vector(arg, make_vector(x, args...)); } void setp(int n) { std::cout << std::fixed << std::setprecision(n); } void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes" : "No") << '\n'; } void No(bool is_not_correct = true) { Yes(!is_not_correct); } void YES(bool is_correct = true) { std::cout << (is_correct ? "YES" : "NO") << '\n'; } void NO(bool is_not_correct = true) { YES(!is_not_correct); } void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; } void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); } #line 2 "/home/kuhaku/atcoder/github/algo/lib/tree/union_find.hpp" /** * @brief 素集合データ構造 * @details Implement (union by size) + (path compression) * @see https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp */ struct union_find { union_find() : data() {} union_find(int _n) : data(_n, -1) {} int root(int x) { return this->data[x] < 0 ? x : this->data[x] = this->root(this->data[x]); } int get_root(int x) { return this->root(x); } bool is_root(int x) const { return this->data[x] < 0; } bool same(int x, int y) { return this->root(x) == this->root(y); } bool is_same(int x, int y) { return this->same(x, y); } int size(int x) { return -(this->data[this->root(x)]); } int get_size(int x) { return this->size(x); } bool unite(int x, int y) { x = this->root(x), y = this->root(y); if (x == y) return false; if (this->data[x] > this->data[y]) std::swap(x, y); this->data[x] += this->data[y]; this->data[y] = x; return true; } template bool unite(int x, int y, F f) { x = this->root(x), y = this->root(y); if (x != y) { if (this->data[x] > this->data[y]) std::swap(x, y); this->data[x] += this->data[y]; this->data[y] = x; } f(x, y); return x != y; } private: std::vector data; }; #line 6 "a.cpp" int main(void) { int n; cin >> n; Graph g(n); g.input_edges(n - 1, 0); union_find uf(n); for (auto &es : g) { for (auto &e : es) uf.unite(e.from(), e.to()); } if (uf.size(0) == n) { co("Bob"); return 0; } LowLink llink(g); if ((uf.size(0) == n - 1 || uf.size(1) == n - 1) && llink.get_bridges().size() == 0) co("Bob"); else co("Alice"); return 0; }