#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,m,fa[maxn<<2],c=1,T,num[maxn<<2],r[maxn<<2];
inline int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
inline void initup(){
memset(r,0,sizeof(r));
memset(fa,0,sizeof(fa));
memset(num,0,sizeof(num));
}
int main(){
//freopen("game.in","w",stdin);
//freopen("game.out","r",stdout);
scanf("%d",&T);
while(T--){
printf("Case #%d\n",c);
initup();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) r[i]=i,fa[i]=i,num[i]=1;
int ans=n,cnt=n;
while(m--){
string s; int x,y;
cin>>s;
if(s[0]=='q') printf("%d\n",ans);
if(s[0]=='f'){
scanf("%d%d",&x,&y);
int xx=find(r[x]),yy=find(r[y]);
if(xx==yy) continue;
if(num[xx]<num[yy]){
num[yy]+=num[xx];
fa[xx]=yy;
ans--;
printf("%d is winner!\n",y);
}
else if(num[xx]>num[yy]){
num[xx]+=num[yy];
fa[yy]=xx;
ans--;
printf("%d is winner!\n",x);
}
else if(num[xx]==num[yy]) printf("Either is winner!\n");
}
if(s[0]=='t'){
scanf("%d%d",&x,&y);
int xx=find(r[x]),yy=find(r[y]);
if(xx!=yy){
if(num[yy]==1) ans--;
r[y]=++cnt;
fa[r[y]]=r[x];
num[xx]++; num[yy]--;
}
}
if(s[0]=='r'){
scanf("%d",&x);
int xx=find(r[x]);
if(num[xx]==1) continue;
num[xx]--;
r[x]=++cnt;
fa[r[x]]=r[x];
num[r[x]]=1;
ans++;
}
}
}
}