#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
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 fa[200005],num[200005],r[200005],n,m,t;
char a[10];
inline int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
inline void init(){
	memset(fa,0,sizeof(fa));
	memset(r,0,sizeof(r));
	memset(num,0,sizeof(num));
}
int main(){
	t=read();
	for(int i=1;i<=t;i++){
		printf("Case #%d:\n",i);
		init();
		n=read(); m=read();
		int ans=n,cnt=n;
		for(int j=1;j<=n;++j) r[j]=j,fa[j]=j,num[j]=1;
		while(m--){
			scanf("%s",a);
			if(a[0]=='q'){
				printf("%d\n",ans);
			}
			if(a[0]=='f'){
				int x=read(),y=read();
				int fx=find(r[x]),fy=find(r[y]);
				if(fx==fy) continue;
				else if(num[fx]>num[fy]){
					printf("%d is winner!\n",x);
					fa[fy]=fx;
					num[fx]+=num[fy];
					ans--;
				}
				else if(num[fy]>num[fx]){
					printf("%d is winner!\n",y);
					fa[fx]=fy;
					num[fy]+=num[fx];
					ans--;
				}
				else if(num[fx]==num[fy]) printf("Either is winner!\n");
			}
			if(a[0]=='t'){
				int x=read(),y=read();
				int fx=find(r[x]),fy=find(r[y]);
				if(fx!=fy){
					r[y]=++cnt;
					fa[r[y]]=fx;
					if(num[fy]==1) ans--;
					num[fy]--;
					num[fx]++;
				}
			}
			if(a[0]=='r'){
				int x=read();
				int fx=find(r[x]);
				if(num[fx]==1) continue;
				num[fx]--;
				r[x]=++cnt;
				fa[r[x]]=r[x];
				num[r[x]]=1;
				ans++;
			}
		}
	}
}