#include <cstdio>
int now_num,bangpai_num;
int fa[400005],size[400005],newwwwww[400005];
char wokao[100005];

inline int gf(int now){
	if(fa[now]==now)	return now;
	return fa[now]=gf(fa[now]);
}

int main(void){
	int t;
	scanf("%d",&t);
	for(int z=1;z<=t;z++){
		printf("Case #%d:\n",z);
		int n,m;
		scanf("%d%d",&n,&m);
		
		for(int i=1;i<=n;i++)	fa[i]=i,size[i]=1,newwwwww[i]=i;
		now_num=n;
		bangpai_num=n;
		
		for(int i=1;i<=m;i++){
			int x,y;
			scanf("%s",&wokao);
			if(wokao[0]!='q'){
				scanf("%d",&x);
				if(wokao[0]!='r')	scanf("%d",&y);
			}
			
			if(wokao[0]=='q')	printf("%d\n",now_num);
			
			else if(wokao[0]=='f'){
				int yx=x,yy=y;
				x=newwwwww[x];
				y=newwwwww[y];
				int fx=gf(x),fy=gf(y);
				if(fx!=fy){
					if(size[fx]!=size[fy]){
						if(size[fx]>size[fy])	printf("%d is winner!\n",yx),size[fx]+=size[fy],size[fy]=0,fa[fy]=fx;
						else 					printf("%d is winner!\n",yy),size[fy]+=size[fx],size[fx]=0,fa[fx]=fy;
						
						now_num--;
					}
					else	printf("Either is winner!\n");
				}
			}
			
			else if(wokao[0]=='t'){
				x=newwwwww[x];
				y=newwwwww[y];
				int fx=gf(x),fy=gf(y);
				if(fx!=fy){
					now_num--;
					size[fx]+=size[fy];
					size[fy]=0;
					fa[fy]=fx;
				}
			}
			
			else if(wokao[0]=='r'){
				int woqu=newwwwww[x];
				int fwoqu=gf(woqu);
				
				if(size[fwoqu]!=1){
					newwwwww[x]=++bangpai_num;
					fa[bangpai_num]=bangpai_num;
					size[fwoqu]--;
					size[bangpai_num]=1;
					now_num++;
				}
			}
		}
		for(int j=1;j<=bangpai_num;j++)	gf(j);
	}
}