#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++;
}
}
}
}