#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,a) for(int i=(int)0;i<(int)a;++i) #define pb push_back #define eb emplace_back using ll=long long; constexpr ll mod = 1e9 + 7; constexpr ll INF = 1LL << 60; 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; } using namespace std; template string to_string(pair p); template string to_string(tuple p); template string to_string(tuple p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template string to_string(bitset v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast('0' + v[i]); } return res; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << "\n"; } template void debug_out(Head H, Tail... T) { cerr << " " <par;//親 vectorRank;//木の深さ vectorsz;//要素数 UF(int n){init(n);} //初期化 void init(int n) { par.resize(n); Rank.resize(n);sz.resize(n); for (int i = 0; i < n; i++) { par[i]= i; Rank[i] = 0; sz[i]=1; } } //木の根を求める int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } //xとyの属する集合を併合 bool unite(int x, int y) { x = find(x); y = find(y); if (x == y)return false;//すでに同じ集合に属している if (Rank[x] < Rank[y]) {//高さが小さい方を下に par[x] = y; sz[y]+=sz[x]; } else { par[y] = x; if (Rank[x] == Rank[y])Rank[x]++;//同じだとrankが変わらないままになるので増やす(それ以外は大きい方のrankが採用される) sz[x]+=sz[y]; } return true; } //xとyが同じ集合に属するかを判定 bool same(int x, int y) { return find(x) == find(y); } int size(int k){//要素数を求める return sz[find(k)]; } }; void solve(){ int n; cin>>n; UF tree(n); vectornum(n); rep(i,n-1){ int u,v; cin>>u>>v; num[u]++; num[v]++; tree.unite(u,v); } int x=tree.size(0); if(x==n)cout<<"Bob\n"; else{ bool flag=false,ng=false; rep(i,n){ if(num[i]==0)flag=true; else if(num[i]!=2)ng=true; } sets; rep(i,n)s.emplace(tree.find(i)); if(!ng&&flag&&s.size()==2)cout<<"Bob\n"; else cout<<"Alice\n"; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout<