#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
const int N = 105;

int n, A;

bitset<N> out[N], in[N], vis;

void bfs(int S, bitset<N> g[N])
{
    queue<int> q;
    q.push(S);
    vis[S] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < n; i++)
        {
            if (g[u][i] && !vis[i])
            {
                vis[i] = true;
                q.push(i);
            }
        }
    }
}

int ans[N];
bool solve()
{
    bitset<N> now, tmp;
    int last = -1;
    for (int i = 0; i < n; i++)
    {
        bool suc = false;
        for (int u = 0; u < n; u++)
        {
            if (now[u]) continue;

            if (~last && !out[last][u])
            {
                if (u == A) continue;
                now[u] = true;

                vis = now;
                bfs(last, out);
                tmp = vis;

                vis = now;
                bfs(A, in);
                tmp = (tmp & vis) & ~now;

                tmp[last] = true;

                bool flag = true;
                for (int v = 0; v < n; v++)
                {
                    if (tmp[v] || now[v]) continue;
                    if ((out[v] & tmp).none())
                    {
                        now[u] = flag = false;
                        break;
                    }
                }

                if (flag)
                {
                    ans[i] = u;
                    suc = true;
                    break;
                }
            }
            else
            {
                if (u != A)
                {
                    vis = now;
                    vis[u] = true;
                    bfs(u, out);
                    tmp = vis;

                    vis = now;
                    vis[u] = true;
                    bfs(A, in);
                    tmp = (tmp & vis) & ~now;
                }
                else
                {
                    tmp.reset();
                    tmp[A] = true;
                }

                bool flag = true;
                for (int v = 0; v < n; v++)
                {
                    if (tmp[v] || now[v]) continue;
                    if ((out[v] & tmp).none())
                    {
                        flag = false;
                        break;
                    }
                }

                if (flag)
                {
                    now[u] = suc = true;
                    ans[i] = last = u;
                    break;
                }
            }
        }
        if (!suc)
            return false;
    }
    return true;
}

int main()
{
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++)
    {
        cin >> n >> A;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                char c;
                scanf(" %c", &c);
                in[i][j] = (c == 'Y');
                out[i][j] = (c == 'N');
            }
        }
        for (int i = 0; i < n; i++)
        {
            out[A][i] = false;
        }
        printf("Case #%d:", t);
        if (!solve())
        {
            printf(" IMPOSSIBLE\n");
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                printf(" %d", ans[i]);
            }
            putchar('\n');
        }
    }
    return 0;
}