#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'){
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",x),size[fx]+=size[fy],size[fy]=0,fa[fy]=fx;
else printf("%d is winner!\n",y),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++;
}
}
}
}
}