#include <bits/stdc++.h>

using namespace std;

using u32=unsigned int;
using i64=long long;
using u64=unsigned long long;
using db=double;
using vi=vector<int>;
using pii=pair<int,int>;

template<typename T>
T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch-'0'),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back

const int N=110;

int n,t;
int g[N][N];
vi e[N],re[N];

int use[N],vis[N];

// int dfn[N],low[N],ti;
// int st[N],tp,ins[N];
// int bl[N],siz[N],scc;
// void dfs(int x){
//     dfn[x]=low[x]=++ti;
//     st[++tp]=x,ins[x]=1;
//     for(auto y:e[x]){
//         if(vis[y]) continue;
//         if(!dfn[y])
//             dfs(y),low[x]=min(low[x],low[y]);
//         else if(ins[y])
//             low[x]=min(low[x],dfn[y]);
//     }
//     if(low[x]==dfn[x]){
//         ++scc;
//         do{
//             bl[st[tp]]=scc,ins[st[tp]]=0;
//             ++siz[scc];
//         }while(st[tp--]!=x);
//     }
// }

bool check(int s,int t){
    // scc=ti=tp=0;
    // for(int i=1;i<=n;i++)
    //     dfn[i]=low[i]=bl[i]=siz[i]=0;
    // for(auto y:re[s])
    //     if(!vis[y]&&y!=t) vis[y]=2;
    // for(int i=1;i<=n;i++)
    //     if(!vis[i]&&!dfn[i]) dfs(i);
    // for(auto y:re[s])
    //     if(vis[y]==2) vis[y]=0;
    // return bl[t]==1;
    if(vis[t]) return false;
    queue<int> q;q.push(t);
    while(!q.empty()){
        int x=q.front();q.pop();
        if(vis[x]) continue;
        vis[x]=2;
        if(x==s) continue;
        for(auto y:re[x])
            if(!vis[y]) q.push(y);
    }
    if(vis[s]){
        for(auto y:re[s])
            if(!vis[y]) vis[y]=2;
    }
    bool ret=!count(vis+1,vis+n+1,0);
    for(int i=1;i<=n;i++)
        if(vis[i]==2) vis[i]=0;
    return ret;
}

int res[N];

void clear(){
    for(int i=1;i<=n;i++){
        use[i]=vis[i]=res[i]=0;
        e[i].clear(),re[i].clear();
        for(int j=1;j<=n;j++) g[i][j]=0;
    }
}

void solve(int id){
    printf("Case #%d: ",id);
    n=rdi(),t=rdi()+1;
    for(int i=1;i<=n;i++){
        static char s[N];scanf("%s",s+1);
        for(int j=1;j<=n;j++)
            if(s[j]=='N') 
                g[i][j]=1,e[i].pb(j),re[j].pb(i);
    }
    int cur=0;
    fill(res+1,res+n+1,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(use[j]) continue;
            int nx=(!cur||g[cur][j]?j:cur);
            vis[cur^j^nx]=1;
            if(check(nx,t)){
                use[j]=1,res[i]=j,cur=nx;
                break;
            }
            vis[cur^j^nx]=0;
        }
        if(!res[i]){
            puts("IMPOSSIBLE");
            clear();return;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<res[i]-1<<" \n"[i==n];
    clear();
}

int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int T=rdi();
    for(int i=1;i<=T;i++) solve(i);
    return 0;
}