#include using namespace std; using ll = long long; template using min_priority_queue = priority_queue, greater>; using pii = pair; using pll = pair; using Graph = vector>; const ll INF = 1LL << 60; template void chmax(T& a, T b) { if (b > a) a = b; } template void chmin(T& a, T b) { if (b < a) a = b; } template std::ostream& operator<<(std::ostream& os, const pair& x) noexcept { return os << "(" << x.first << ", " << x.second << ")"; } template void print_vector(vector a) { cout << '['; for (int i = 0; i < a.size(); i++) { cout << a[i]; if (i != a.size() - 1) { cout << ", "; } } cout << ']' << endl; } class UnionFind { public: // コンストラクタ UnionFind(); UnionFind(int); // 根を求める int root(int x) const; // x と y が同じグループに属するかどうか (根が一致するかどうか) bool issame(int x, int y) const; // x を含むグループと y を含むグループとを併合する bool unite(int x, int y); // 要素の追加。まだ追加されていない要素だったらその要素だけから成る集合を作る void add_elem(int x); // x を含むグループのサイズ int size(int x) const; // 島の個数 int n_unions() const; // 要素xがすでに追加されているかどうかを判定 bool is_added(int x) const; private: // 経路圧縮する。根を返す int path_compression(int x); std::vector parents; std::vector sizes; }; // コンストラクタ UnionFind::UnionFind() {} UnionFind::UnionFind(int N) { parents = std::vector(N, -1); sizes = std::vector(N, -1); } // 根を求める int UnionFind::root(int x) const { if (parents[x] == -1) return x; // x が根の場合は x を返す return root(parents[x]); } // x と y が同じグループに属するかどうか (根が一致するかどうか) bool UnionFind::issame(int x, int y) const { return root(x) == root(y); } // x を含むグループと y を含むグループとを併合する bool UnionFind::unite(int x, int y) { // x, y をそれぞれ根まで移動する if (!is_added(x)) sizes[x] = 1; if (!is_added(y)) sizes[y] = 1; int root_x = path_compression(x); int root_y = path_compression(y); // すでに同じグループのときは何もしない if (root_x == root_y) return false; if (!is_added(root_x)) sizes[root_x] = 1; if (!is_added(root_y)) sizes[root_y] = 1; // union by size (y 側のサイズが小さくなるようにする) if (sizes[root_x] < sizes[root_y]) std::swap(root_x, root_y); // y を x の子とする parents[root_y] = root_x; sizes[root_x] += sizes[root_y]; return true; } void UnionFind::add_elem(int x) { // すでに追加されていたら何もしない if (is_added(x)) return; sizes[x] = 1; } // x を含むグループのサイズ。x が追加されていない要素の場合は「1」を返す int UnionFind::size(int x) const { if (is_added(x)) return sizes[root(x)]; return 1; } // 島の個数 int UnionFind::n_unions() const { std::unordered_set s; for (size_t i = 0; i < sizes.size(); i++) if (is_added(i)) s.insert(root(i)); return s.size(); } // 経路圧縮をしながら根を求める int UnionFind::path_compression(int x) { if (parents[x] == -1) return x; // x が根の場合は x を返す parents[x] = path_compression(parents[x]); return parents[x]; } bool UnionFind::is_added(int x) const { return sizes[x] != -1; } pll make_edge(ll a, ll b) { return {min(a, b), max(a, b)}; } void count_nodes_and_edges_core(Graph& G, int current, unordered_set& seen, set& edges) { seen.insert(current); for (auto& v : G[current]) { edges.insert(make_edge(current, v)); if (seen.count(v)) continue; count_nodes_and_edges_core(G, v, seen, edges); } } // 無向グラフGについて、頂点iを含む連結成分におけるノード数をエッジ数をカウント pll count_nodes_and_edges(Graph& G, int i) { unordered_set seen; set edges; count_nodes_and_edges_core(G, i, seen, edges); return {seen.size(), edges.size()}; } void dfs(Graph& g, int current, unordered_set& seen, bool& is_ok) { if (g[current].size() != 2) is_ok = false; seen.insert(current); for (auto& v : g[current]) { if (seen.count(v)) continue; dfs(g, v, seen, is_ok); } } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); ll N; cin >> N; Graph G(N); auto uf = UnionFind(N); for (int i = 0; i < N; i++) { uf.add_elem(i); } for (int i = 0; i < N - 1; i++) { ll a, b; cin >> a >> b; // std::cout << a << ' ' << b << "\n"; uf.unite(a, b); G[a].push_back(b); G[b].push_back(a); } // for (int i = 0; i < N; i++) { // std::cout << uf.root(i) << "\n"; // } // std::cout << uf.n_unions() << "\n"; if (uf.n_unions() == 1) { std::cout << "Bob" << "\n"; return 0; } if (uf.n_unions() >= 3) { std::cout << "Alice" << "\n"; return 0; } unordered_set seen; for (int i = 0; i < N; i++) { if (uf.size(i) == 1) continue; if (seen.count(uf.root(i))) continue; auto tmp = count_nodes_and_edges(G, i); // std::cout << i << "\n"; if (tmp.first != tmp.second) { // 輪っかでない std::cout << "Alice" << "\n"; return 0; } if (tmp.first == tmp.second) { unordered_set seen2; bool is_ok = true; dfs(G, i, seen2, is_ok); if (!is_ok) { // 輪っかでない std::cout << "Alice" << "\n"; return 0; } } seen.insert(uf.root(i)); } std::cout << "Bob" << "\n"; return 0; }