#include using namespace std; /* STEP 1: 木DPですべての部分木についての grundy 数を求める. この後で, 問題の要求に答えることは相対的に簡単である. STEP 2: 木DPで持つべきは, 1. dp[i] := i の部分木の grundy 数 2. ep[i] := i の部分木であって, 頂点 i をパスに使用している場合の grundy 数の集合. 更新について: i の子の集合を S とする. X = xor {dp[j] | j∈S} としよう. F = ∪[j∈S]{e^dp[j]^X | e ∈ ep[j]} ∪ {X} とする. ep[i] は F, dp[i] は mex{F}. ep[i] の要素数が最大で数十万になることから, ここが律速であると間に合わない. この問題の真の姿は, ep[i] を高速に管理するデータ構造を考える問題である. 要素の追加・全部にxor・mex が高速にできるデータ構造を用意すれば, そのまま「マージテク」の形をしているので解決できる. そして, そのデータ構造として適しているのは, binary trie である. mex はやや厄介だが, 「x番目の要素はxである」を満たす最大のxを二分探索で求めればよい. mex は頻繁に呼ばれないため, ここは少し遅くても問題ない. (実際 mex の部分は O(N log^2 N) 時間) time : O(N log^2 N) space : O(N log N) */ template struct binary_trie { struct node { node *ch[2] = {nullptr, nullptr}; int cnt = 0; node() {} }; public: node *root = nullptr; int xor_all = 0; binary_trie() : root(nullptr) {} void insert(int val){ val ^= xor_all; root = insert(root, val); } int count(int val){ node* now_node = root; val ^= xor_all; for (int b=MAX_LOG-1; b>=0; b--){ if (now_node == nullptr) break; now_node = now_node->ch[(val>>b)&1]; } return size(now_node); } int xth(int x){ node* now_node = root; assert(now_node != nullptr); int ret = 0; for (int b=MAX_LOG-1; b>=0; b--){ bool f = (xor_all>>b)&1; if (size(now_node->ch[f]) <= x){ x -= size(now_node->ch[f]); now_node = now_node->ch[f^1]; ret = (ret<<1)|(f^1); }else{ assert(1 <= size(now_node->ch[f])); now_node = now_node->ch[f]; ret = (ret<<1)|f; } } return ret ^ xor_all; } int mex(){ int ub = root->cnt; int lb = -1; while (ub - lb > 1){ int t = (ub + lb) / 2; if (xth(t) == t) lb = t; else ub = t; } return lb + 1; } private: node* insert(node* t, int val, int b = MAX_LOG - 1){ if (t == nullptr) t = new node; t->cnt++; if (b < 0) return t; bool f = (val>>b)&1; t->ch[f] = insert(t->ch[f], val, b-1); return t; } int size(node* t){ if (t == nullptr) return 0; return t->cnt; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector> ikeru(n, vector(0)); for (int i=0; i> u >> v; u--; v--; ikeru[u].push_back(v); ikeru[v].push_back(u); } vector dp(n); vector> ep(n); auto dfs1 = [&](auto self, int i, int p) -> void { int x = 0; int mxval = 0; int mxind = i; for (int j: ikeru[i]){ if (j == p) continue; self(self, j, i); x ^= dp[j]; if (mxval < ep[j].root->cnt) { mxval = ep[j].root->cnt; mxind = j; } } ep[mxind].xor_all ^= dp[mxind]^x; for (int j: ikeru[i]){ if (j == p) continue; if (j == mxind) { continue; }else{ int mxz = ep[j].root->cnt; for (int z=0; z ans; auto dfs2 = [&](auto self, int i, int p, int g) -> void { int x = g; for (int j: ikeru[i]){ if (j == p) continue; x ^= dp[j]; } if (x == 0) ans.push_back(i); for (int j: ikeru[i]){ if (j == p) continue; self(self, j, i, x^dp[j]); } }; dfs2(dfs2, 0, -1, 0); if (ans.empty()){ cout << "Bob\n"; }else{ cout << "Alice\n"; int k = ans.size(); sort(ans.begin(), ans.end()); cout << k << '\n'; for (int x: ans){ cout << x+1 << ' '; } cout << '\n'; } }