\(n\le 10^5\)

首先森林的每个连通块肯定是独立的，算出 \(SG\) 异或一下就行了
对于 \(SG(u)\) 的计算，如果只是从子树中的节点 \(v\) 的 SG 值转移来，式子将会很复杂，也不太能优化
因为 \(SG(u)\) 最后的形式是对一个集合取 \(\operatorname{mex}\)，考虑直接维护这个集合

找出 \(\operatorname{subtree}(u)\) 的所有的后继状态：

• 如果删除的点是 \(u\)，那么后继状态的 SG 就是 \(\operatorname{XOR}_{(u,v)\in E} SG(v)\)，把这玩意插入 \(u\) 的集合中就行
• 如果删除的点在子树 \(v\) 中，那么其他子树 \(k\) 都不会受影响，有 \(\operatorname{XOR}_{(u,k)\in E,v\neq k} SG(v)\)，而 \(v\) 子树形成的若干连通块的异或值都在 \(v\) 的集合中
• 于是就是把 \(v\) 的集合中的所有数，都异或上 \(\operatorname{XOR}_{(u,k)\in E,v\neq k} SG(v)\)，然后全插入到集合 \(u\) 中

于是需要一个数据结构，支持全局异或、快速合并、单点插入、全局求 \(\operatorname{mex}\)
发现直接上一个 trie 来合并就行

#define N 100006
#define M 200006
struct Graph{
	int fir[N],nex[M],to[M],tot;
	inline void add(int u,int v,int flag=1){
		to[++tot]=v;
		nex[tot]=fir[u];fir[u]=tot;
		if(flag) add(v,u,0);
	}
	inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
}G;
struct Node{
	Node *son[2];
	int tag,all;
	inline void pushdown(int now){
		son[0]->tag^=tag;son[1]->tag^=tag;
		if((tag>>now)&1) std::swap(son[0],son[1]);
		tag=0;
	}
}*root[N],*null,dizhi[N*22];int tot;
inline void pushup(Node *x){x->all=(x->son[0]->all&&x->son[1]->all);}
inline void init(Node *&x){x=&dizhi[tot++];x->son[0]=x->son[1]=null;x->tag=x->all=0;}
inline void init(){
	std::memset(dizhi,0,tot*sizeof dizhi[0]);tot=0;
	init(null);
}
#define MAX 18
void insert(Node *&tree,int x,int now=MAX){
	if(tree==null) init(tree);
	if(!~now) return tree->all=1,void();
	tree->pushdown(now);
	insert(tree->son[(x>>now)&1],x,now-1);
	pushup(tree);
}
int mex(Node *tree,int now=MAX){
	if(tree==null||!~now) return 0;
	tree->pushdown(now);
	return mex(tree->son[tree->son[0]->all],now-1)|(tree->son[0]->all<<now);
}
Node *merge(Node *a,Node *b,int now=MAX){
	if(a==null) return b;
	if(b==null) return a;
	a->pushdown(now);b->pushdown(now);
	a->son[0]=merge(a->son[0],b->son[0],now-1);
	a->son[1]=merge(a->son[1],b->son[1],now-1);
	if(~now) pushup(a);
	return a;
}
int sg[N],vis[N];
void dfs(int u,int fa=0){
	root[u]=null;vis[u]=1;
	int sum=0;
	for(int i=G.fir[u];i;i=G.nex[i])if(G.to[i]^fa) dfs(G.to[i],u),sum^=sg[G.to[i]];
	for(int v,i=G.fir[u];i;i=G.nex[i])if(G.to[i]^fa){
		v=G.to[i];
		root[v]->tag^=sum^sg[v];
//			mex(root[v]);
//			printf("u=%d v=%d  mex(v)=%d\n",u,v,mex(root[v]));
		root[u]=merge(root[u],root[v]);
	}
	insert(root[u],sum);
	sg[u]=mex(root[u]);
}
int main(){
//		freopen("20.in","r",stdin);
int $=read();while($--){
	int n=read(),m=read();G.clear();
	for(int i=1;i<=m;i++) G.add(read(),read());
	init();std::memset(vis,0,(n+1)*sizeof vis[0]);
	int ans=0;
	for(int i=1;i<=n;i++)if(!vis[i]) dfs(i),ans^=sg[i];
//		for(int i=1;i<=n;i++) write(i),write(" : "),write(sg[i]),EN;
	write(ans?"Alice\n":"Bob\n");
}
	return SUC_RETURN;
}