#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template ostream &operator<<(ostream &os, const vector &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") // !!!Watch out for stack overflow!!! // Meldable // 0 for null, ts[0] = T() // chPoint(u, a, f, args...): point update // chRange(u, a, b, f, args...): range update s.t. T() -> T() // T::push(T *l, T *r) // T::pull(const T &l, const T &r) // T::meld(const T &t): meld leaf T's // Manages the number of elements (as a set). template struct Seg { static constexpr int NUM_NODES = 1 << 23; int h; int nodesLen; int nxt[NUM_NODES][2]; T ts[NUM_NODES], lz[NUM_NODES]; void init(int h_) { h = h_; nodesLen = 1; nxt[0][0] = nxt[0][1] = 0; ts[0] = T(); lz[0] = T(); } int newNode() { assert(nodesLen < NUM_NODES); const int u = nodesLen++; nxt[u][0] = nxt[u][1] = 0; ts[u] = T(0); lz[u] = T(0); return u; } // u: height e void ch(int e, int u, T t) { if (u) { if (e && (t >> (e - 1) & 1)) swap(nxt[u][0], nxt[u][1]); lz[u] ^= t; } } void ch(int u, T t) { ch(h, u, t); } // u: height (e+1) void push(int e, int u) { if (lz[u]) { ch(e, nxt[u][0], lz[u]); ch(e, nxt[u][1], lz[u]); lz[u] = 0; } } void pull(int u) { ts[u] = ts[nxt[u][0]] + ts[nxt[u][1]]; } int build(T a) { assert(0 <= a); assert(a < T(1) << h); const int u = nodesLen; for (int e = 0; e <= h; ++e) ts[newNode()] = T(1); for (int e = 0; e < h; ++e) nxt[u + (e + 1)][a >> e & 1] = u + e; return u + h; } T mex(int u) { if (ts[u] == T(1) << h) return T(1) << h; T a = 0; for (int e = h; --e >= 0; ) { push(e, u); if (ts[nxt[u][0]] == T(1) << e) { a |= T(1) << e; u = nxt[u][1]; } else { u = nxt[u][0]; } } return a; } // Frees v. int meld(int e, int u, int v) { if (!u) return v; if (!v) return u; if (!e) { ts[u] |= ts[v]; return u; } --e; push(e, u); push(e, v); nxt[u][0] = meld(e, nxt[u][0], nxt[v][0]); nxt[u][1] = meld(e, nxt[u][1], nxt[v][1]); pull(u); return u; } int meld(int u, int v) { return meld(h, u, v); } // Does not push. void print(int e, T a, int u) { if (!u) return; cerr << string(2 * (h - e), ' ') << u << " [" << a << ", " << (a | T(1) << e) << ") " << ts[u] << " " << lz[u] << endl; if (!e) return; --e; print(e, a, nxt[u][0]); print(e, a | T(1) << e, nxt[u][1]); } void print(int u) { if (!u) cerr << "[Seg::print] null" << endl; print(h, T(0), u); } // Pushes string toString(int e, T a, int u) { if (!u) return ""; if (!e) return to_string(a) + ","; --e; push(e, u); return toString(e, a, nxt[u][0]) + toString(e, a | T(1) << e, nxt[u][1]); } string toString(int u) { return "{" + toString(h, T(0), u) + "}"; } }; int N; vector A, B; vector> graph; pair> slow(int u, int p) { int sum = 0; vector xs{0}; for (const int v : graph[u]) if (p != v) { const auto res = slow(v, u); sum ^= res.first; for (const int x : res.second) xs.push_back(x ^ res.first); } for (int &x : xs) x ^= sum; sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int x = 0; ; ++x) { if (!(x < (int)xs.size() && xs[x] == x)) { cerr<<"[slow] "< dp; Seg seg; int dfs(int u, int p) { int sum = 0; int ret = seg.build(0); for (const int v : graph[u]) if (p != v) { const int res = dfs(v, u); sum ^= dp[v]; // cerr<<__LINE__<<": "< ans; void DFS(int u, int p, int now) { now ^= dp[u]; for (const int v : graph[u]) if (p != v) now ^= dp[v]; if (!now) { ans.push_back(u); } for (const int v : graph[u]) if (p != v) { DFS(v, u, now); } now ^= dp[u]; for (const int v : graph[u]) if (p != v) now ^= dp[v]; } int main() { for (; ~scanf("%d", &N); ) { A.resize(N - 1); B.resize(N - 1); for (int i = 0; i < N - 1; ++i) { scanf("%d%d", &A[i], &B[i]); --A[i]; --B[i]; } graph.assign(N, {}); for (int i = 0; i < N - 1; ++i) { graph[A[i]].push_back(B[i]); graph[B[i]].push_back(A[i]); } int E; for (E = 0; !(N < 1 << E); ++E) {} seg.init(E); dp.assign(N, -1); dfs(0, -1); if (dp[0]) { ans.clear(); DFS(0, -1, dp[0]); puts("Alice"); printf("%d\n", (int)ans.size()); for (int h = 0; h < (int)ans.size(); ++h) { if (h) printf(" "); printf("%d", ans[h] + 1); } puts(""); } else { puts("Bob"); } #ifdef LOCAL slow(0,-1); #endif } return 0; }