#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100005;
int fa[maxn<<1],size[maxn<<1],mapped[2*maxn],hui[2*maxn];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,m,x,y,fx,fy,cnt,next;
int getfa(int x){
	if(fa[x]==x)return x;
	return fa[x]=getfa(fa[x]);
}
int main(){
	int t;
	t=read();
	for(int k=1;k<=t;k++){
		printf("Case #%d:\n",k);
		memset(mapped,0,sizeof(mapped));
		n=read();m=read();
		for(int i=1;i<=n;i++){fa[i]=i;size[i]=1;mapped[i]=i;}
		cnt=n;
		int shu_bangpai=n;
		for(int i=1;i<=m;i++){
			char s[105];
			scanf("%s",s);
			if(s[0]=='q')printf("%d\n",shu_bangpai);
			if(s[0]=='f){
				x=read();y=read();
				fx=getfa(mapped[x]);fy=getfa(mapped[y]);
				if(fx==fy)continue;
				if(size[fx]==size[fy]){
					printf("Either is winner!\n");
					continue;
				}
				shu_bangpai--;
				if(size[fx]>size[fy]){
					size[fx]+=size[fy];
					//size[fy]=0;
					fa[fy]=fx;
					printf("%d is winner!\n",x);
					continue;
				}
				if(size[fx]<size[fy]){
					size[fy]+=size[fx];
					//size[fx]=0;
					fa[fx]=fy;
					printf("%d is winner!\n",y);
					continue;
				}
			}
			if(s=='t'){//x诱惑y 
				x=read();y=read();
				fx=getfa(mapped[x]),fy=getfa(mapped[y]);
				if(fx==fy)continue;
				if(size[fy]==1)shu_bangpai--;
				mapped[y]=++cnt;
				fa[mapped[y]]=mapped[x];
				size[fx]++;
				size[fy]--;
			}
			if(s=='r'){//反叛,传位。 
				x=read();
				fx=getfa(mapped[x]);
				if(size[fx]==1)continue;
				size[fx]--;
				mapped[x]=++cnt;
				fa[mapped[x]]=mapped[x];
				size[mapped[x]]=1;
				shu_bangpai++;
			}
		}
	}
}