#include <bits/stdc++.h>
using namespace std;
const int N=105;
int T,n,A,ok;
char input[N];
int g0[N][N];
int used[N];
int ans[N];
int vis[N];
bool dfs(int u){
	//printf("hi! %d\n",u);
	vis[u] = 1;
	if(u==A) return 1;
	for(int v=0;v<n;v++){
		if(!g0[u][v] || used[v] || vis[v]) continue;
		if(dfs(v)) return 1;
	}
	return 0;
}
bool chk(int u){
	//printf("checking %d\n",u);
	for(int x=0;x<n;x++){
		if((used[x] && x!=u) || g0[x][u]) continue;
		memset(vis,0,sizeof(vis));
		//printf("%d dfs!\n",x);
		if(!dfs(x)) return 0;
	}
	return 1;
}
void dfs(int cur,int fa){
	if(cur==n+1){
		ok = 1;
		return;
	}
	for(int u=0;u<n;u++){
		if(used[u]) continue;
		//cout<<"hiiiiiiiiiiiiii!   "<<cur<<' '<<u<<endl;
		used[u] = 1;
		if(fa!=-1 && g0[u][fa] && chk(fa)){
			ans[cur] = u;
			dfs(cur+1,fa);
			return;
		}
		else if(chk(u)){
			ans[cur] = u;
			dfs(cur+1,u);
			return;
		}
		used[u] = 0;
	}
}
int main(){
	scanf("%d",&T);//initialize the arrays
	for(int tt=1;tt<=T;tt++){
		scanf("%d%d",&n,&A);
		ok = 0;
		memset(g0,0,sizeof(g0));
		memset(used,0,sizeof(used));
		for(int i=0;i<n;i++){
			scanf("%s",input);
			for(int j=0;j<n;j++)
				if(input[j]=='N')
					g0[i][j] = 1;
		}
		dfs(1,-1);
		printf("Case #%d: ",tt);
		if(!ok) puts("IMPOSSIBLE");
		else{
			for(int i=1;i<=n;i++)
				printf("%d ",ans[i]);
			puts("");
		}
	}
	return 0;
}