#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int T,n,A,cater,nw,length,in[N+1],p[N+1],q[N+1],belong[N+1];
char c[N+1][N+1];
bool used[N+1];
bool cmp(int x,int y)
{
    return in[x]<in[y];
}
int get_max(int x,int y)
{
    if (!x||!y) return x^y;
    return (c[x][y]=='N')?y:x;
}
bool check(int x)
{
    int res=0,ps=1;
    if (!used[A])
    {
	length=0;
	for (int i=1;i<=n;++i)
	    if (!used[i])
		p[++length]=i;
	sort(p+1,p+length+1,cmp);
	for (int i=1;i<=length;++i)
	{
	    res+=in[p[i]];
	    if (res==((i*(i-1))>>1))
	    {
		++cater;
		for (int t=ps;t<=i;++t) belong[p[t]]=cater;
		ps=i+1;
	    }
	}
	for (int i=1;i<=n;++i)
	    if ((!x||c[x][i]=='N')&&belong[i]>belong[A])
		return 0;
	return 1;
    }
    else
    {
	if (get_max(nw,A)!=A) return 0;
	for (int i=1;i<=n;++i)
	    if (!used[i]&&c[A][i]=='N')
		return 0;
	return 1;
    }
}
int main()
{
    T=read();
    for (int i=1;i<=T;++i)
    {
	n=read(),A=read()+1,nw=0;
	for (int j=1;j<=n;++j) in[j]=used[j]=0;
	for (int j=1;j<=n;++j)
	    for (int k=1;k<=n;++k)
	    {
		cin>>c[j][k];
		if (c[j][k]=='N') in[k]++;
	    }
	if (!check(0))
	{
	    printf("Case #%d: IMPOSSIBLE\n",i);
	    continue;
	}
	for (int j=1;j<=n;++j)
	{
 	    for (int k=1;k<=n;++k)
		if (!used[k])
		{
		    for (int t=1;t<=n;++t)
			if (!used[t]&&c[k][t]=='N')
			    in[t]--;
		    used[k]=1;
		    if (check(get_max(nw,k)))
		    {
			q[j]=k;
			break;
		    }
		    used[k]=0;
		    for (int t=1;t<=n;++t)
			if (!used[t]&&c[k][t]=='N')
			    in[t]++;
		}
	    nw=get_max(nw,q[j]);
	}
	printf("Case #%d: ",i);
	for (int j=1;j<=n;++j) printf("%d ",q[j]-1);
	puts("");
    }
    return 0;
}