#define MOD_TYPE 1 #pragma region Macros #include using namespace std; #if 1 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #if 0 #include #include #include #include using namespace __gnu_pbds; using namespace __gnu_cxx; template using extset = tree, rb_tree_tag, tree_order_statistics_node_update>; #endif #if 0 #include #include using Int = boost::multiprecision::cpp_int; using lld = boost::multiprecision::cpp_dec_float_100; #endif using ll = long long int; using ld = long double; using pii = pair; using pll = pair; using pld = pair; template using smaller_queue = priority_queue, greater>; constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353); constexpr int INF = (int)1e9 + 10; constexpr ll LINF = (ll)4e18; constexpr ld PI = acos(-1.0); constexpr ld EPS = 1e-7; constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0}; constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0}; #define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i) #define rep(i, n) REP(i, 0, n) #define REPI(i, m, n) for (int i = m; i < (int)(n); ++i) #define repi(i, n) REPI(i, 0, n) #define MP make_pair #define MT make_tuple #define YES(n) cout << ((n) ? "YES" : "NO") << "\n" #define Yes(n) cout << ((n) ? "Yes" : "No") << "\n" #define possible(n) cout << ((n) ? "possible" : "impossible") << "\n" #define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n" #define all(v) v.begin(), v.end() #define NP(v) next_permutation(all(v)) #define dbg(x) cerr << #x << ":" << x << "\n"; struct io_init { io_init() { cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(30) << setiosflags(ios::fixed); }; } io_init; template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } inline ll CEIL(ll a, ll b) { return (a + b - 1) / b; } template inline void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } template constexpr istream &operator>>(istream &is, pair &p) noexcept { is >> p.first >> p.second; return is; } template constexpr ostream &operator<<(ostream &os, pair &p) noexcept { os << p.first << " " << p.second; return os; } #pragma endregion random_device seed_gen; mt19937_64 engine(seed_gen()); // -------------------------------------- struct UnionFind { public: UnionFind() : _n(0) {} UnionFind(int n) : _n(n), parent_or_size(n, -1) {} int unite(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = root(a), y = root(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return root(a) == root(b); } int root(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = root(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[root(a)]; } vector> groups() { vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = root(i); group_size[leader_buf[i]]++; } vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector &v) { return v.empty(); }), result.end()); return result; } private: int _n; vector parent_or_size; }; void solve() { int n; cin >> n; vector> E(n); vector deg(n, 0); UnionFind uf(n); rep(i, n - 1) { int u, v; cin >> u >> v; uf.unite(u, v); E[u].push_back(v); E[v].push_back(u); deg[u]++, deg[v]++; } set roots; rep(i, n) roots.insert(uf.root(i)); if (roots.size() >= 3) { cout << "Alice\n"; return; } else if (roots.size() == 1) { cout << "Bob\n"; return; } auto itr = roots.begin(); int a = *itr; itr++; int b = *itr; if (uf.size(a) >= 2 and uf.size(b) >= 2) { cout << "Alice\n"; return; } // ループかチェック rep(i, n) { if (deg[i] == 1) { cout << "Alice\n"; return; } } cout << "Bob\n"; } int main() { solve(); }