#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("input2.txt","r",stdin);
    freopen("output2.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;
}