#include <cstdio>
#include <cstring>
using namespace std;

inline int read() {
    int x=0,f=1;
    char cr=getchar();
    while (cr>'9' || cr<'0') {
        if (cr=='-') f=-1;
        cr=getchar();
    }
    while (cr>='0' && cr<='9') {
        x=(x<<3)+(x<<1)+cr-'0';
        cr=getchar();
    }
    return x*f;
}

const int maxn=100005;

char a[10];

int real[maxn<<2],fa[maxn<<2],size[maxn<<2];

inline int getf(int k) {
    return fa[k]==k ? k : fa[k]=getf(fa[k]);
}

inline void file() {
	freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
}

inline void _remove() {
	memset(real,0,sizeof(real));
	memset(fa,0,sizeof(fa));
	memset(size,0,sizeof(size));
}

int main() {
	//file();
	int t=read();
	for (int cao=1;cao<=t;cao++) {
		printf("Case #%d:\n",cao);
	_remove();
    int n=read(),m=read();
    for (int i=1;i<=n;i++) real[i]=fa[i]=i,size[i]=1;
    int tot=n;
    int cnt=n;
    for (int i=1;i<=m;i++) {
        scanf("%s",a);
        if (a[0]=='q') printf("%d\n",tot);
        if (a[0]=='f') {
            int x=read(),y=read();
            int fx=getf(real[x]),fy=getf(real[y]);
            if (fx==fy) continue;
            if (size[fx]>size[fy]) {
                size[fx]+=size[fy];
                fa[fy]=fx;
                tot--;
                printf("%d is winner!\n",x);
                continue;
            }
            if (size[fx]<size[fy]) {
                size[fy]+=size[fx];
                fa[fx]=fy;
                tot--;
                printf("%d is winner!\n",y);
                continue;
            }
            if (size[fx]==size[fy]) {
                printf("Either is winner!\n");
                continue;
            }
        }
        if (a[0]=='t') {
            int x=read(),y=read();
            int fx=getf(real[x]),fy=getf(real[y]);
            if (fx!=fy) {
                real[y]=++cnt;
                fa[real[y]]=real[x];
                size[fx]++;
                if (size[fy]==1) tot--;
            }
        }
        if (a[0]=='r') {
            int x=read(),fx=getf(real[x]);
            size[fx]--;
            if (!size[fx]) tot--;
            real[x]=++cnt;
            fa[real[x]]=real[x];
            size[real[x]]=1;
       	    tot++;          
       	}
    	}
	}
}