#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int pre[3*maxn],num[3*maxn],id[3*maxn];
int cnt;
int n,m;
int ans;
void init()
{
cnt = n,ans = n;
for(int i = 1;i <=3*n;++i)
{
pre[i] = i;
num[i] = 1;
id[i] = i;
}
return ;
}
int find(int x)
{
return x==pre[x] ? x : pre[x] = find(pre[x]);
}
void join(int x,int y)
{
int f1=find(x),f2=find(y);
if(f1 != f2)
{
pre[f2] = f1;
num[f1] += num[f2];
ans--;
}
return ;
}
void del(int x)
{
int f = find(id[x]);
num[f]--;
if(num[f]==0)
ans--;
cnt++;
num[cnt] = 1;
pre[cnt] = cnt;
id[x] = cnt;
ans++;
return ;
}
int main()
{
int _;
cin>>_;
char s[10];
int ca = 1;
while(_--)
{
scanf("%d %d",&n,&m);
init();
printf("Case #%d:\n",ca++);
for(int i = 1; i<= m;++i)
{
scanf("%s",s);
if(s[0]=='q')
{
printf("%d\n",ans);
}
else if(s[0] =='f')
{
int x,y;
scanf("%d %d",&x,&y);
int f1 = find(id[x]);
int f2 = find(id[y]);
if(f1 == f2)
continue;
if(num[f1] > num[f2])
{
printf("%d is winner!\n",x);
join(id[x],id[y]);
}
else if(num[f1] < num[f2])
{
printf("%d is winner!\n",y);
join(id[y],id[x]);
}
else
printf("Either is winner!\n");
}
else if(s[0] =='t')
{
int x,y;
scanf("%d %d",&x,&y);
del(y);
join(id[x],id[y]);
}
else if(s[0] =='r')
{
int x;
scanf("%d",&x);
del(x);
}
}
}
return 0;
}