Description
Alice和Bob在玩游戏。有n个节点，m条边(0<=m<=n-1)，构成若干棵有根树，每棵树的根节点是该连通块内编号最
小的点。Alice和Bob轮流操作，每回合选择一个没有被删除的节点x，将x及其所有祖先全部删除，不能操作的人输
。注：树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。比如：1-3-2 这样一条链
，1号点是根节点，删除1号点之后，3号点还是2号点的父节点。问有没有先手必胜策略。n约为10w。
显然只要算出每颗子树的sg值就可以计算答案了，考虑自底向上推出sg值，用trie维护当前子树中，删去一条从根开始的链后得到的每种情况的sg值（即为与这条链相邻的子树的sg值的异或和）构成的集合，于是可以查询mex，通过trie的合并可以构建出当前点的父亲对应的集合，另外要通过打标记实现整棵trie异或上一个值。
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=;
int T,n,m;
int es[N*],enx[N*],e0[N],ed[N],ep=,f[N];
int sz[N*],ch[N*][],xt[N*],rt[N],p=;
void tag(int w,int h,int v){
if(w&&h>=&&v){
xt[w]^=v;
if(v>>h&)std::swap(ch[w][],ch[w][]);
}
}
void dn(int w,int h){
if(xt[w]){
tag(ch[w][],h-,xt[w]);
tag(ch[w][],h-,xt[w]);
xt[w]=;
}
}
int mex(int w){
int s=;
for(int i=,d;~i;--i){
dn(w,i);
if(sz[ch[w][]]==(<<i))w=ch[w][],s|=<<i;
else w=ch[w][];
}
return s;
}
int build(int x){
int rt=++p,w;
sz[w=rt]=;
for(int i=;~i;--i)sz[w=ch[w][x>>i&]=++p]=;
return rt;
}
int merge(int a,int b,int h){
if(!a||!b)return a|b;
dn(a,h);dn(b,h);
ch[a][]=merge(ch[a][],ch[b][],h-);
ch[a][]=merge(ch[a][],ch[b][],h-);
sz[a]=h>=?sz[ch[a][]]+sz[ch[a][]]:;
return a;
}
void dfs(int w,int pa){
ed[w]=;
int x=;
for(int i=e0[w],u;i;i=enx[i]){
u=es[i];
if(u!=pa){
dfs(u,w);
x^=f[u];
}
}
for(int i=e0[w],u;i;i=enx[i]){
u=es[i];
if(u!=pa){
tag(rt[u],,x);
rt[w]=merge(rt[w],rt[u],);
}
}
rt[w]=merge(rt[w],build(x),);
f[w]=mex(rt[w]);
tag(rt[w],,f[w]);
}
int _(){
int x=,c=getchar();
while(c<)c=getchar();
while(c>)x=x*+c-,c=getchar();
return x;
}
int main(){
for(T=_();T;--T){
if(p){
memset(ch,,sizeof(ch[])*(p+));
memset(sz,,sizeof(int)*(p+));
memset(xt,,sizeof(int)*(p+));
p=;
}
n=_();m=_();
for(int i=;i<=n;++i)e0[i]=ed[i]=f[i]=rt[i]=;
ep=;
for(int i=,a,b,c;i<m;++i){
a=_();b=_();
es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;
es[ep]=a;enx[ep]=e0[b];e0[b]=ep++;
}
for(int i=;i<=n;++i)if(!ed[i]){
dfs(i,);
f[]^=f[i];
}
puts(f[]?"Alice":"Bob");
}
return ;
}