#include <cstdio>
#include <cstring>
#include <iostream>
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]=i,fa[i]=i,size[i]=1;
    	int tot=n,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);
            	}
            	else if (size[fx]<size[fy]) {
                	size[fy]+=size[fx];
                	fa[fx]=fy;
                	tot--;
                	printf("%d is winner!\n",y);
            	}
				else if (size[fx]==size[fy]) printf("Either is winner!\n");
			}
        	if (a[0]=='t') {
            	int x=read(),y=read();
            	int fx=getf(real[x]),fy=getf(real[y]);
            	if (fx!=fy) {
       		        if (size[fy]==1) tot--;
            	    real[y]=++cnt;
       	    	    fa[real[y]]=real[x];
        	        size[fx]++;
        	        size[fy]--;
       		    }
        	}
        	if (a[0]=='r') {
        	    int x=read(),fx=getf(real[x]);
        	    if (size[fx]==1) continue;
				size[fx]--;
        	    real[x]=++cnt;
        	    fa[real[x]]=real[x];
				size[real[x]]=1;
				tot++;
       		}
    	}
	}
}