#include <bits/stdc++.h>
using namespace std;
typedef long long int LL ;
const int MOD = 1e9+7;
const int N = 100000+5;
void fre(){
freopen("input5.txt","r",stdin);
freopen("output5.txt","w",stdout);
}
inline int read(){
int f=1,x=0;char ch = getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
return f*x;
}
/*********************************************************************/
int pre[N<<1],h[N],son[N<<1],cnt,ans,n,m;
int findi(int x){
int r = x;
while(r!=pre[r]) r=pre[r];
int i = x,j;
while(i!=r){
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void join(int x,int y){
int fx = findi(h[x]),fy = findi(h[y]);
if(fx==fy) return;
int temp = ans;
if(son[fx]<son[fy]) pre[fx]=fy,son[fy]+=son[fx],ans--,printf("%d",y);
if(son[fy]<son[fx]) pre[fy]=fx,son[fx]+=son[fy],ans--,printf("%d",x);
if(temp == ans) printf("Either");
puts(" is winner!");
return;
}
void creat(int now){
h[now]=++cnt;
pre[cnt]=cnt;
son[cnt]=1;
ans++;
}
char s[10];
int main(){
// fre();
int _=1,kcase = 0;
scanf("%d",&_);
while(_--){
scanf("%d%d",&n,&m);
cnt = 0,ans = 0;
for(int i=1;i<=n;i++) creat(i);
printf("Case #%d:\n",++kcase);
for(int x,y;m--;){
scanf("%s",s);
if('q'==s[0]){//query
printf("%d\n",ans);
}
else if('f'==s[0]){//fight
scanf("%d%d",&x,&y);
join(x,y);
}
else if('t'==s[0]){//tempt
scanf("%d%d",&x,&y);
int fx = findi(h[x]),fy = findi(h[y]);
if(fx==fy) continue;
son[fy]--,son[fx]++;
if(!son[fy]) ans--;
creat(y);
pre[h[y]]=fx;
ans--;
}
else if('r'==s[0]){//revolt
scanf("%d",&x);
int fx = findi(h[x]);
if(son[fx]==1) continue;
son[fx]--;creat(x);
}
}
}
return 0;
}