#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
bool del[105];
int deg[105], e[105][105], n, a;
void Add(int u, int w) {
	for (int i = 1; i <= n; i++) if (!e[u][i] && i != u) deg[i] += w;
	del[u] = w != 1;
}
struct P {
	int u, d;
	bool operator<(const P &b) const { return d < b.d; }
} p[105];
int pC;
int C(int u, int v) { return e[u][v] ? v : u; }
bool Chk(int s) {
	pC = 0;
	for (int i = 1; i <= n; i++) if (!del[i]) p[++pC] = { i, deg[i] };
	sort(p + 1, p + pC + 1);
	bool flg = false, anyE = false;
	for (int i = 1, x = 0, las = 0; i <= n; i++) {
		anyE |= e[s][p[i].u];
		x += p[i].d;
		if (x == i * (i - 1) / 2) {
			bool hasA = false;
			for (int j = las + 1; j <= i; j++) hasA |= (p[j].u == a);
			if (hasA) flg = true;
			if (!flg) {
				for (int j = las + 1; j <= i; j++) if (!e[p[j].u][s]) return false;
			}
			las = i;
		}
	}
	return anyE || s == a;
}
int main() {
	scanf("%d", &T);
	for (int tid = 1; tid <= T; tid++) {
		printf("Case #%d: ", tid);
		memset(del, 0, sizeof(del));
		memset(deg, 0, sizeof(deg));
		int cur = 0;
		scanf("%d%d", &n, &a), a++;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				char c; scanf(" %c", &c);
				e[i][j] = (c == 'N');
				deg[i] += e[i][j];
			}
			e[0][i] = true;
		}
		if (!Chk(0)) puts("IMPOSSIBLE");
		else {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (!del[j]) {
						Add(j, -1);
						if (Chk(C(cur, j))) {
							cur = C(cur, j);
							printf("%d%c", j - 1, " \n"[i == n]);
							break;
						}
						Add(j, 1);
					}
				}
			}
		}
	}
	return 0;
}