//Code by juju527.
#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<int,int>
#define fi first
#define se second
#define vec vector<int>
#define eb emplace_back
using namespace std;
const int maxn=105;
int n,a;
char s[maxn];
bool e[maxn][maxn];
int cd[maxn];
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<48||ch>57){if(ch==45)y=-1;ch=getchar();}
	while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
pii buf[maxn];
bool use[maxn];
inline int trans(int p,int x){
	if(!p)return x;
	return e[p][x]?x:p;
}
int it[maxn];
bool chk(int x){
	if(x==a){
		for(int i=1;i<=n;i++)if(!use[i]&&e[a][i])return 0;
		return 1;
	}
	int len=0;
	for(int i=1;i<=n;i++)if(!use[i])buf[++len]=pii(cd[i],i);
	sort(buf+1,buf+len+1);
	int sum=0,scc=0,pos;
	for(int i=1;i<=len;i++){
		sum+=buf[i].fi;if(buf[i].se==a)pos=i;
		if(sum==i*(i-1)/2)it[++scc]=i;
	}
	int p=0;
	for(int i=1;i<=scc;i++)if(it[i]<pos)p=i;
	for(int i=1;i<=it[p];i++)if(e[x][buf[i].se])return 0;
	return 1;
}
int main(){
	int T,cas=0;
	T=read();
	while(T--){
		n=read(),a=read()+1;
		for(int i=1;i<=n;i++){
			scanf("%s",s+1);
			for(int j=1;j<=n;j++)e[i][j]=(s[j]=='N');
		}
		for(int i=1;i<=n;i++){
			cd[i]=0;
			for(int j=1;j<=n;j++)cd[i]+=e[i][j];
			buf[i]=pii(cd[i],i);
		}
		sort(buf+1,buf+n+1);
		int sum=0;bool ok=0;
		for(int i=1;i<=n;i++){
			sum+=buf[i].fi;ok|=(buf[i].se==a);
			if(sum==i*(i-1)/2)break;
		}
		if(!ok){printf("Case #%d: IMPOSSIBLE\n",++cas);continue;}
		for(int i=1;i<=n;i++)use[i]=0;
		int p=0;
		printf("Case #%d: ",++cas);
		for(int i=1;i<=n;i++){
			for(int x=1;x<=n;x++){
				if(use[x])continue;
				int z=trans(p,x);
				if(x==a&&z!=a)continue;
				use[x]=1;
				for(int u=1;u<=n;u++)if(!use[u])cd[u]-=e[u][x];
				if(chk(z)){p=z;printf("%d ",x-1);break;}
				for(int u=1;u<=n;u++)if(!use[u])cd[u]+=e[u][x];
				use[x]=0;
			}
		}
		puts("");
	}
    return 0;
}