Your friend Salem is Warawreh's brother and only loves math and geometry problems. He has solved plenty of such problems, but according to Warawreh, in order to graduate from university he has to solve more graph problems. Since Salem is not good with graphs he asked your help with the following problem.

You are given a complete directed graph with $n$ vertices without self-loops. In other words, you have $n$ vertices and each pair of vertices $u$ and $v$ ($u \neq v$) has both directed edges $(u, v)$ and $(v, u)$.

Every directed edge of the graph is labeled with a single character: either 'a' or 'b' (edges $(u, v)$ and $(v, u)$ may have different labels).

You are also given an integer $m > 0$. You should find a path of length $m$ such that the string obtained by writing out edges' labels when going along the path is a palindrome. The length of the path is the number of edges in it.

You can visit the same vertex and the same directed edge any number of times.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 1000$; $1 \leq m \leq 10^{5}$) — the number of vertices in the graph and desirable length of the palindrome.

Each of the next $n$ lines contains $n$ characters. The $j$-th character of the $i$-th line describes the character on the edge that is going from node $i$ to node $j$.

Every character is either 'a' or 'b' if $i \neq j$, or '*' if $i = j$, since the graph doesn't contain self-loops.

It's guaranteed that the sum of $n$ over test cases doesn't exceed $1000$ and the sum of $m$ doesn't exceed $10^5$.


-----Output-----

For each test case, if it is possible to find such path, print "YES" and the path itself as a sequence of $m + 1$ integers: indices of vertices in the path in the appropriate order. If there are several valid paths, print any of them.

Otherwise, (if there is no answer) print "NO".


-----Examples-----

Input
5
3 1
*ba
b*b
ab*
3 3
*ba
b*b
ab*
3 4
*ba
b*b
ab*
4 6
*aaa
b*ba
ab*a
bba*
2 6
*a
b*
Output
YES
1 2
YES
2 1 3 2
YES
1 3 1 3 1
YES
1 2 1 3 4 1 4
NO


-----Note-----

The graph from the first three test cases is shown below:

In the first test case, the answer sequence is $[1,2]$ which means that the path is:

$$1 \xrightarrow{\text{b}} 2$$

So the string that is obtained by the given path is b.

In the second test case, the answer sequence is $[2,1,3,2]$ which means that the path is:

$$2 \xrightarrow{\text{b}} 1 \xrightarrow{\text{a}} 3 \xrightarrow{\text{b}} 2$$

So the string that is obtained by the given path is bab.

In the third test case, the answer sequence is $[1,3,1,3,1]$ which means that the path is:

$$1 \xrightarrow{\text{a}} 3 \xrightarrow{\text{a}} 1 \xrightarrow{\text{a}} 3 \xrightarrow{\text{a}} 1$$

So the string that is obtained by the given path is aaaa.

The string obtained in the fourth test case is abaaba.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms

Implementation

Greedy algorithms

Complete search


Solutions:
import collections
import string
import math
import copy
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
mo = 998244353

def exgcd(a, b):
	if not b:
		return (1, 0)
	(y, x) = exgcd(b, a % b)
	y -= a // b * x
	return (x, y)

def getinv(a, m):
	(x, y) = exgcd(a, m)
	return --1 if x == 1 else x % m

def comb(n, b):
	res = 1
	b = min(b, n - b)
	for i in range(b):
		res = res * (n - i) * getinv(i + 1, mo) % mo
	return res % mo

def quickpower(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mo
		n >>= 1
		a = a * a % mo
	return res

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def getpref(x):
	if x > 1:
		return x * (x - 1) >> 1
	else:
		return 0

def orafli(upp):
	primes = []
	marked = [False for i in range(upp + 3)]
	for i in range(2, upp):
		if not marked[i]:
			primes.append(i)
		for j in primes:
			if i * j >= upp:
				break
			marked[i * j] = True
			if i % j == 0:
				break
	return primes
t = int(input())
for ti in range(t):
	(n, m) = map(int, input().split())
	mp = []
	ap = [[] for i in range(n)]
	bp = [[] for i in range(n)]

	def scan(p, col):
		for i in range(n):
			if mp[p][i] == col:
				return True
		return False
	for i in range(n):
		mp.append(input())
	master = -1
	for i in range(n):
		for j in range(i + 1, n):
			if mp[i][j] == mp[j][i]:
				master = (i + 1, j + 1)
				break
	if m == 1:
		print('YES')
		print('1 2')
		continue
	if master != -1:
		print('YES')
		for i in range(m + 1):
			print(master[i % 2], end='')
			if i == m:
				print()
			else:
				print(' ', end='')
	elif m & 1 == 0:
		if n == 2:
			print('NO')
			continue
		else:
			print('YES')
			(x, y, z) = (1, 2, 3)
			if mp[1][0] != mp[1][2]:
				(x, y) = (y, x)
			elif mp[2][0] != mp[2][1]:
				(x, z) = (z, x)
			if m >> 1 & 1:
				for i in range(m >> 1):
					print([x, y][(i + 1) % 2], end=' ')
				for i in range(m >> 1):
					print([x, z][i % 2], end=' ')
				print(f'{z}')
			else:
				for i in range(m >> 1):
					print([x, y][i % 2], end=' ')
				for i in range(m >> 1):
					print([x, z][i % 2], end=' ')
				print(f'{x}')
	else:
		print('YES')
		for i in range(m + 1):
			print(i % 2 + 1, end='')
			if i == m:
				print()
			else:
				print(' ', end='')


from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
for CASES in range(int(input())):
	space = input().split()
	(n, m) = map(int, space)
	MAP = []
	for i in range(n):
		MAP.append(input().strip())
	black = True
	ans = []
	cir1 = -2
	cir2 = -2
	for i in range(n):
		for j in range(n):
			if i > j and MAP[i][j] == MAP[j][i]:
				(cir1, cir2) = (i, j)
	charm = -2
	chara = -2
	charb = -2
	for i in range(n):
		if len(set(MAP[i])) == 3:
			charm = i
			for j in range(n):
				if MAP[i][j] == 'a':
					chara = j
				elif MAP[i][j] == 'b':
					charb = j
	charm += 1
	chara += 1
	charb += 1
	cir1 += 1
	cir2 += 1
	if m % 2 == 1:
		for i in range(m + 1):
			if i % 2 == 1:
				ans.append(1)
			else:
				ans.append(2)
	elif cir1 != -1:
		for i in range(m + 1):
			if i % 2 == 1:
				ans.append(cir1)
			else:
				ans.append(cir2)
	elif charm != -1:
		if m % 4 == 0:
			for i in range(m + 1):
				if i % 2 == 0:
					ans.append(charm)
				elif i % 4 == 1:
					ans.append(chara)
				elif i % 4 == 3:
					ans.append(charb)
		else:
			for i in range(m + 1):
				if i % 2 == 1:
					ans.append(charm)
				elif i % 4 == 0:
					ans.append(chara)
				elif i % 4 == 2:
					ans.append(charb)
	else:
		black = False
	if not black:
		print('NO')
		continue
	print('YES')
	for i in range(m + 1):
		print(ans[i], end=' ')
	print()


import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	X = [[0 if a == 'a' else 1 if a == 'b' else -1 for a in input()] for _ in range(N)]
	if M % 2:
		print('YES')
		print(*[1, 2] * (M // 2 + 1))
		continue
	f = 0
	for i in range(N):
		for j in range(i):
			if X[i][j] == X[j][i]:
				print('YES')
				print(*[i + 1] + [j + 1, i + 1] * (M // 2))
				f = 1
				break
		if f:
			break
	if f:
		continue
	if N == 2:
		print('NO')
		continue
	if X[0][1] == X[1][2]:
		(i, j, k) = (1, 2, 3)
	elif X[1][2] == X[2][0]:
		(i, j, k) = (2, 3, 1)
	else:
		(i, j, k) = (3, 1, 2)
	print('YES')
	if M % 4:
		print(*[i] + [j, i] * (M // 4) + [j, k] * (M // 4 + 1))
	else:
		print(*[j, i] * (M // 4) + [j, k] * (M // 4) + [j])


import os
import sys
from io import BytesIO, IOBase

def solve():
	(n, m) = map(int, input().split())
	a = [list(input().rstrip()) for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if i != j and a[i][j] == a[j][i]:
				print('YES')
				print(*[i + 1 if k % 2 else j + 1 for k in range(m + 1)])
				return
	if m & 1:
		print('YES')
		print(*[1 if k % 2 else 2 for k in range(m + 1)])
		return
	for i in range(1, n):
		for j in range(n):
			if i != j:
				if a[0][i] == a[i][j]:
					print('YES')
					b = [1, i + 1, j + 1, i + 1]
					if not m % 4:
						b = [i + 1, j + 1, i + 1, 1]
					print(*[b[k % 4] for k in range(m + 1)])
					return
				elif a[i][0] == a[0][j]:
					print('YES')
					b = [i + 1, 1, j + 1, 1]
					if not m % 4:
						b = [1, j + 1, 1, i + 1]
					print(*[b[k % 4] for k in range(m + 1)])
					return
	print('NO')

def main():
	for _ in range(int(input())):
		solve()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
t = int(stdin.readline())

def run():
	L = [int(x) for x in stdin.readline().split(' ')]
	(n, m) = (L[0], L[1])
	M = []
	for i in range(n):
		M.append(stdin.readline())
	if m % 2 == 1:
		res = []
		for k in range(m):
			res.append(1)
			res.append(2)
		res = res[:m + 1]
		print('YES')
		print(' '.join([str(x) for x in res]))
		return
	for i in range(n):
		for j in range(i + 1, n):
			if M[i][j] == M[j][i]:
				res = []
				for k in range(m):
					res.append(i + 1)
					res.append(j + 1)
				res = res[:m + 1]
				print('YES')
				print(' '.join([str(x) for x in res]))
				return
	if n == 2:
		print('NO')
		return
	(fi, fj, fk) = (-1, -1, -1)
	for i in range(3):
		for j in range(3):
			for k in range(3):
				if i != j and j != k and (i != k):
					if M[i][j] == M[j][k]:
						fi = i
						fj = j
						fk = k
	md = m // 2
	if md % 2 == 0:
		pattern = [fj, fi, fj, fk]
		res = pattern * m
		res = res[:m + 1]
	else:
		pattern = [fi, fj, fk, fj]
		res = pattern * m
		res = res[:m + 1]
	print('YES')
	print(' '.join([str(x + 1) for x in res]))
for _ in range(t):
	run()


from collections import Counter
import itertools
t = int(input())
for tc in range(1, t + 1):
	(n, m) = map(int, input().split())
	g = []
	acs = []
	bcs = []
	res = []
	if m == 1:
		res = [1, 2]
	for i in range(n):
		if res:
			_ = input()
		else:
			r = input().replace(' ', '')
			if i > 0:
				for j in range(i):
					if r[j] == g[j][i]:
						if m % 2 == 0:
							res = [i + 1, j + 1] * (m // 2)
							res.append(i + 1)
						else:
							res = [i + 1, j + 1] * ((m + 1) // 2)
						break
			if not res:
				ac = r.count('a')
				acs.append(ac)
				bcs.append(n - 1 - ac)
				g.append(r)
	if not res:
		if m % 2 == 1:
			if m % 2 == 0:
				res = [1, 2] * (m // 2)
				res.append(1)
			else:
				res = [1, 2] * ((m + 1) // 2)
		elif m == 2:
			for i in range(n):
				for j in range(n):
					if i != j:
						c = g[i][j]
						k = g[j].find(c)
						if k != -1:
							res = [i + 1, j + 1, k + 1]
							break
				if res:
					break
		else:
			for rs in itertools.permutations(range(n), 3):
				c0 = g[rs[0]][rs[1]]
				c1 = g[rs[1]][rs[2]]
				if c0 == c1:
					c2 = g[rs[2]][rs[0]]
					if c1 == c2:
						l = [rs[0] + 1, rs[1] + 1, rs[2] + 1]
						res = l * ((m + 1) // 3)
						res.extend(l[:(m + 1) % 3])
						break
			for (x, y, z) in itertools.permutations(range(n), 3):
				fs = []
				ss = []
				f = g[x][y]
				s = g[y][z]
				if f == s:
					fs.append(x)
					ss.append(z)
					find = False
					l = 2
					r = 0
					c = 0
					while l < m and l >= 2:
						if r == x:
							r += 1
						elif c == z:
							c += 1
						elif r >= n:
							r = 0
							c += 1
						elif c >= n:
							x = fs.pop() + 1
							z = ss.pop()
							r = 0
							c = 0
							l -= 2
						elif x >= n:
							x = 0
							z += 1
							r = 0
							c = 0
						elif z >= n:
							x = fs.pop() + 1
							z = ss.pop()
							r = 0
							c = 0
							l -= 2
						else:
							f = g[r][x]
							s = g[z][c]
							if f == s:
								fs.append(r)
								ss.append(c)
								x = r
								z = c
								r = 0
								c = 0
								l += 2
							else:
								r += 1
					if l == m:
						res = map(lambda x: x + 1, list(reversed(fs)) + [y] + ss)
						break
	if res:
		print('YES')
		print(' '.join(map(str, res)))
	else:
		print('NO')


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
for f in range(int(input())):
	(n, m) = map(int, input().split())
	e = []
	for i in range(n):
		e.append(input())
	if n == 2:
		if m % 2:
			print('YES')
			print(*[1, 2] * (m // 2 + 1))
		elif e[0][1] == e[1][0]:
			print('YES')
			print(*[1, 2] * (m // 2) + [1])
		else:
			print('NO')
	elif m % 2:
		print('YES')
		print(*[1, 2] * (m // 2 + 1))
	else:
		good = False
		for i in range(2):
			for j in range(i + 1, 3):
				if e[i][j] == e[j][i]:
					good = True
					gi = i + 1
					gj = j + 1
		if good:
			print('YES')
			print(*[gi, gj] * (m // 2) + [gi])
		else:
			for i in range(3):
				for j in range(3):
					if j != i:
						for k in range(3):
							if k != i and k != j and (e[i][j] == e[j][k]):
								gi = i + 1
								gj = j + 1
								gk = k + 1
			print('YES')
			if m % 4 == 2:
				print(*[gi] + [gj, gk, gj, gi] * (m // 4) + [gj, gk])
			else:
				print(*[gj, gk, gj, gi] * (m // 4) + [gj])


import sys, os, io
from collections import defaultdict
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	grid = []
	for i in range(n):
		grid.append(list(input().strip()))
	(a, b) = (0, 0)
	flag = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if grid[i][j] == grid[j][i]:
				(a, b) = (i + 1, j + 1)
				flag = 1
				break
	if flag == 1:
		ans = []
		for i in range(m + 1):
			if i % 2:
				ans.append(a)
			else:
				ans.append(b)
		print('YES')
		print(*ans)
		continue
	elif m % 2:
		ans = []
		for i in range(m + 1):
			if i % 2:
				ans.append(1)
			else:
				ans.append(2)
		print('YES')
		print(*ans)
	else:
		if n == 2:
			print('NO')
			continue
		(a, b, c, d) = (0, 0, 0, 0)
		if grid[0][1] == grid[1][2]:
			a = 0
			b = 1
			c = 2
		elif grid[1][2] == grid[2][0]:
			a = 1
			b = 2
			c = 0
		elif grid[2][0] == grid[0][1]:
			a = 2
			b = 0
			c = 1
		a += 1
		b += 1
		c += 1
		if m % 4 == 0:
			ans = []
			for i in range(m + 1):
				if i % 4 == 0:
					ans.append(b)
				elif i % 4 == 1:
					ans.append(c)
				elif i % 4 == 2:
					ans.append(b)
				elif i % 4 == 3:
					ans.append(a)
			print('YES')
			print(*ans)
			continue
		else:
			ans = []
			print('YES')
			for i in range(m + 1):
				if i % 4 == 0:
					ans.append(a)
				elif i % 4 == 1:
					ans.append(b)
				elif i % 4 == 2:
					ans.append(c)
				elif i % 4 == 3:
					ans.append(b)
			print(*ans)


import math
from collections import defaultdict, Counter
from itertools import permutations

def fact(n):
	return 1 if n == 1 or n == 0 else n * fact(n - 1)

def prime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def inp():
	l = list(map(int, input().split()))
	return l

def main():
	for _ in range(int(input())):
		(n, m) = inp()
		g = []
		for j in range(n):
			g.append(input())
		solve(n, m, g)

def solve(n, m, g):
	ans = []
	for i in range(n):
		for j in range(n):
			if i != j and g[i][j] == g[j][i]:
				ans = ([i + 1, j + 1] * m)[:m + 1]
				print('YES')
				print(*ans)
				return
	if m % 2:
		print('YES')
		ans = ([1, 2] * m)[:m + 1]
		print(*ans)
		return
	if n == 2:
		print('NO')
		return
	for c in permutations(range(3), 3):
		(i, j, k) = c
		if g[i][j] == g[j][k]:
			break
	print('YES')
	ans = ([i + 1, j + 1] * (m // 2))[:m // 2][::-1] + [j + 1] + ([k + 1, j + 1] * (m // 2))[:m // 2]
	print(*ans)
	return
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	(N, M) = getInts()
	grid = [listStr() for j in range(N)]
	if M % 2 == 1:
		ans = []
		for i in range(M + 1):
			if i % 2 == 0:
				ans.append(1)
			else:
				ans.append(2)
		print('YES')
		print(*ans)
		return
	a_out = [-1] * N
	a_in = [-1] * N
	b_out = [-1] * N
	b_in = [-1] * N
	for i in range(N):
		for j in range(N):
			if i == j:
				continue
			if grid[i][j] == grid[j][i]:
				ans = []
				for k in range(M + 1):
					if k % 2 == 0:
						ans.append(i + 1)
					else:
						ans.append(j + 1)
				print('YES')
				print(*ans)
				return
			if grid[i][j] == 'a':
				a_out[i] = j
				a_in[j] = i
			else:
				b_out[i] = j
				b_in[j] = i
	if N == 2:
		print('NO')
		return
	for i in range(N):
		if a_out[i] >= 0 and a_in[i] >= 0:
			(x, y, z) = (i + 1, a_out[i] + 1, a_in[i] + 1)
			ans = []
			if M % 4 == 0:
				for j in range(M + 1):
					if j % 2 == 0:
						ans.append(x)
					elif j % 4 == 1:
						ans.append(y)
					else:
						ans.append(z)
			else:
				for j in range(M + 1):
					if j % 2 == 1:
						ans.append(x)
					elif j % 4 == 0:
						ans.append(z)
					else:
						ans.append(y)
		elif b_out[i] >= 0 and b_in[i] >= 0:
			(x, y, z) = (i + 1, b_out[i] + 1, b_in[i] + 1)
			ans = []
			if M % 4 == 0:
				for j in range(M + 1):
					if j % 2 == 0:
						ans.append(x)
					elif j % 4 == 1:
						ans.append(y)
					else:
						ans.append(z)
			else:
				for j in range(M + 1):
					if j % 2 == 1:
						ans.append(x)
					elif j % 4 == 0:
						ans.append(z)
					else:
						ans.append(y)
	print('YES')
	print(*ans)
	return
for _ in range(getInt()):
	solve()


import sys
max_int = 2147483648
min_int = -max_int
t = int(input())
for _t in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	m += 1
	M = []
	s_out = []
	for nn in range(n):
		s = input()
		M.append(s)
		s_out.append(set(list(s)))
	if not m % 2:
		print('YES')
		print(('1 2 ' * (m // 2)).strip())
		continue
	has_to_break = False
	same = ()
	s_in = [set() for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			s_in[j].add(M[i][j])
			s_in[i].add(M[j][i])
			if M[i][j] == M[j][i]:
				same = (i, j)
				has_to_break = True
				break
		if has_to_break:
			break
	if same:
		print('YES')
		tmp = str(same[0] + 1) + ' ' + str(same[1] + 1) + ' '
		tmp *= m // 2
		if m % 2:
			tmp += str(same[0] + 1)
		else:
			tmp = tmp.strip()
		print(tmp)
		continue
	has_to_break = False
	for i in range(n):
		for ch in ('a', 'b'):
			(p1, p2, p3) = (-1, -1, -1)
			if ch in s_in[i] and ch in s_out[i]:
				p2 = i
			else:
				continue
			for j in range(n):
				if M[p2][j] == ch:
					p3 = str(j + 1)
					break
			for j in range(n):
				if M[j][p2] == ch:
					p1 = str(j + 1)
					break
			if p1 == -1 or p3 == -1:
				continue
			p2 = str(p2 + 1)
			if not m % 2:
				out = (p1 + ' ' + p2 + ' ') * (m // 2)
			else:
				h = m // 2
				if h % 2:
					out = (p1 + ' ' + p2 + ' ') * (h // 2) + p1 + ' ' + p2 + ' ' + p3 + (' ' + p2 + ' ' + p3) * (h // 2)
				else:
					out = (p2 + ' ' + p1 + ' ') * (h // 2) + p2 + (' ' + p3 + ' ' + p2) * (h // 2)
			print('YES')
			print(out.strip())
			has_to_break = True
			break
		if has_to_break:
			break
	else:
		print('NO')


def main():
	cases = int(input())
	ans_list = []
	for _ in range(cases):
		(n, m) = map(int, input().split(' '))
		graph = []
		for i in range(n):
			graph.append(input())
		pair = None
		for i in range(n):
			for j in range(i + 1, n):
				if graph[i][j] == graph[j][i]:
					pair = (i + 1, j + 1)
					break
			if pair is not None:
				break
		cur_ans = []
		if pair is not None:
			while m >= 0:
				cur_ans.append(str(pair[m % 2]))
				m -= 1
			ans_list.append('YES')
			ans_list.append(' '.join(map(str, cur_ans)))
		elif m % 2 == 1:
			while m >= 0:
				cur_ans.append(m % 2 + 1)
				m -= 1
			ans_list.append('YES')
			ans_list.append(' '.join(map(str, cur_ans)))
		elif n == 2:
			ans_list.append('NO')
		else:
			start = None
			(my_a, my_b) = (None, None)
			for i in range(n):
				if 'a' in graph[i] and 'b' in graph[i]:
					start = i + 1
					my_a = graph[i].index('a') + 1
					my_b = graph[i].index('b') + 1
					break
			if m % 4 == 0:
				cur_ans.append(start)
				cur_index = 0
				while m > 0:
					if cur_index == 0:
						cur_ans.append(my_b)
					elif cur_index == 1:
						cur_ans.append(start)
					elif cur_index == 2:
						cur_ans.append(my_a)
					else:
						cur_ans.append(start)
					m -= 1
					cur_index += 1
					cur_index %= 4
			else:
				cur_index = 0
				cur_ans.append(my_a)
				while m > 0:
					if cur_index == 0 or cur_index == 2:
						cur_ans.append(start)
					elif cur_index == 1:
						cur_ans.append(my_b)
					else:
						cur_ans.append(my_a)
					m -= 1
					cur_index += 1
					cur_index %= 4
			ans_list.append('YES')
			ans_list.append(' '.join(map(str, cur_ans)))
	print('\n'.join(ans_list))
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, M, graph):

	def check(ans):
		if DEBUG:
			pal = []
			for (i, j) in zip(ans, ans[1:]):
				pal.append(graph[i][j])
			assert pal == pal[::-1]
			assert len(pal) == M
	for u in range(N):
		for v in range(u + 1, N):
			if graph[u][v] == graph[v][u] or M % 2 == 1:
				cycle = [u, v]
				ans = [cycle[i % 2] for i in range(M + 1)]
				check(ans)
				return 'YES\n' + ' '.join((str(i + 1) for i in ans))
	assert M % 2 == 0

	def f(ch):
		assert M % 2 == 0
		g = [[] for i in range(N)]
		gT = [[] for i in range(N)]
		cycle = None
		for u in range(N):
			for v in range(N):
				if graph[u][v] == ch:
					assert u != v
					if g[v]:
						w = g[v].pop()
						assert w != u and w != v
						cycle = [u, v, w]
						break
					elif gT[u]:
						w = gT[u].pop()
						assert w != u and w != v
						cycle = [w, u, v]
						break
					g[u].append(v)
					gT[v].append(u)
		if cycle:
			assert len(cycle) == 3
			start = -((M - 1) // 2)
			ans = [cycle[(start + i) % 3] for i in range(M + 1)]
			check(ans)
			return 'YES\n' + ' '.join((str(i + 1) for i in ans))
		else:
			return None
	return f('a') or f('b') or 'NO'
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(100000):
		N = random.randint(2, 10)
		graph = [['ab'[random.randint(0, 1)] for i in range(N)] for j in range(N)]
		for i in range(N):
			graph[i][i] = '*'
		M = random.randint(1, 100)
		print('tc', _, N, M, graph)
		ans = solve(N, M, graph)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	graph = [input().decode().rstrip() for i in range(N)]
	ans = solve(N, M, graph)
	print(ans)


import sys
input = sys.stdin.readline
from itertools import permutations

def solution(n, m, mat):
	sol = []
	if m % 2 == 1:
		print('YES')
		for i in range(m + 1):
			sol.append(i % 2 + 1)
		print(*sol)
		return
	elif n == 2 and mat[0][1] != mat[1][0]:
		print('NO')
		return
	elif n == 2:
		print('YES')
		for i in range(m + 1):
			sol.append(i % 2 + 1)
		print(*sol)
		return
	else:
		for [u, v] in [[0, 1], [0, 2], [1, 2]]:
			if mat[u][v] == mat[v][u]:
				print('YES')
				for i in range(m + 1):
					sol.append([u, v][i % 2] + 1)
				print(*sol)
				return
		for [u, v, w] in permutations([0, 1, 2]):
			if mat[u][v] == mat[v][w]:
				left = [[v + 1, w + 1, v + 1, u + 1][i % 4] for i in range((m - 2) // 2)]
				left.reverse()
				middle = [u + 1, v + 1, w + 1]
				right = [[v + 1, u + 1, v + 1, w + 1][i % 4] for i in range((m - 2) // 2)]
				sol += left
				sol += middle
				sol += right
				print('YES')
				print(*sol)
				return
T = int(input())
for t in range(T):
	[n, m] = list(map(int, input().split()))
	mat = [input() for _ in range(n)]
	solution(n, m, mat)


def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase

def solve(n, m, lab):
	if m == 1:
		print('YES')
		print(1, 2)
		return
	for i in range(n):
		for j in range(i + 1, n):
			if lab[i][j] == lab[j][i]:
				print('YES')
				a = [i + 1, j + 1] * (m // 2 + 1)
				if not m & 1:
					a.pop()
				print(*a)
				return
	if n == 2:
		if m & 1:
			print('YES')
			a = [1, 2] * (m // 2 + 1)
			print(*a)
			return
		else:
			print('NO')
			return
	for i in range(n):
		for j in range(n):
			xx = (i - 1) % n
			if j == xx or j == i:
				continue
			if lab[xx][i] != lab[i][j] and m & 1 or (lab[xx][i] == lab[i][j] and (not m & 1)):
				print('YES')
				a = [xx + 1, i + 1, j + 1, i + 1]
				if not m & 1:
					if not m % 4:
						a = [i + 1, xx + 1, i + 1, j + 1]
				ans = [a[jj % 4] for jj in range(m + 1)]
				print(*ans)
				return
	print('YES')
	a = list(range(1, n + 1))
	ans = [a[jj % n] for jj in range(m + 1)]
	print(*ans)
	return

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		lab = [input().strip() for _ in range(n)]
		solve(n, m, lab)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


from sys import stdin, stdout
input = stdin.readline

def f1(i, j, k):
	global all
	if mat[i][j] == mat[j][k] and mat[j][i] == mat[k][j]:
		all = []
		for p in range(m // 2 + 1):
			if p % 2 == 0:
				all.append(i + 1)
			else:
				all.append(j + 1)
		all.pop()
		for p in range(m // 2 + 1):
			if p % 2 == 0:
				all.append(j + 1)
			else:
				all.append(k + 1)
		return True
	return False

def f2(i, j, k):
	global all
	if mat[i][j] == mat[j][k] and mat[j][i] == mat[k][j]:
		all = []
		for p in range(m // 2 + 1):
			if p % 2 == 0:
				all.append(j + 1)
			else:
				all.append(i + 1)
		all.pop()
		for p in range(m // 2 + 1):
			if p % 2 == 0:
				all.append(j + 1)
			else:
				all.append(k + 1)
		return True
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mat = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		s = input()[:-1]
		for j in range(n):
			mat[i][j] = s[j]
	if m % 2:
		print('YES')
		for i in range(m + 1):
			if i % 2:
				stdout.write(str(1) + ' ')
			else:
				stdout.write(str(2) + ' ')
		print()
		continue
	pivot = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if mat[i][j] == mat[j][i]:
				pivot = 1
				a = i + 1
				b = j + 1
				print('YES')
				for k in range(m + 1):
					if k % 2:
						stdout.write(str(a) + ' ')
					else:
						stdout.write(str(b) + ' ')
				print()
				break
		if pivot:
			break
	if pivot:
		continue
	if n == 2:
		print('no')
		continue
	print('yes')
	if m // 2 % 2:
		all = []
		f1(0, 1, 2)
		if len(all) > 0:
			print(*all)
			continue
		f1(0, 2, 1)
		if len(all) > 0:
			print(*all)
			continue
		f1(1, 0, 2)
		if len(all) > 0:
			print(*all)
			continue
		f1(1, 2, 0)
		if len(all) > 0:
			print(*all)
			continue
		f1(2, 0, 1)
		if len(all) > 0:
			print(*all)
			continue
		f1(2, 1, 0)
		if len(all) > 0:
			print(*all)
			continue
	else:
		all = []
		f2(0, 1, 2)
		if len(all) > 0:
			print(*all)
			continue
		f2(0, 2, 1)
		if len(all) > 0:
			print(*all)
			continue
		f2(1, 0, 2)
		if len(all) > 0:
			print(*all)
			continue
		f2(1, 2, 0)
		if len(all) > 0:
			print(*all)
			continue
		f2(2, 0, 1)
		if len(all) > 0:
			print(*all)
			continue
		f2(2, 1, 0)
		if len(all) > 0:
			print(*all)
			continue


for testcase in range(int(input())):
	arr = [int(x) for x in input().split()]
	(n, m) = (arr[0], arr[1])
	graph = []
	for i in range(n):
		graph.append(input())
	if m & 1 == 1:
		print('YES')
		for i in range(m + 1):
			if i & 1 == 1:
				print(2, end=' ')
			else:
				print(1, end=' ')
		print()
		continue
	flag = False
	for i in range(n):
		for j in range(n):
			if i != j:
				if graph[i][j] == graph[j][i]:
					print('YES')
					for k in range(m + 1):
						if k & 1 == 1:
							print(j + 1, end=' ')
						else:
							print(i + 1, end=' ')
					print()
					flag = True
					break
		if flag:
			break
	else:
		flag = False
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if i != j and j != k and (k != i):
						if graph[i][j] == graph[j][k]:
							print('YES')
							if m // 2 % 2 == 1:
								r = m // 2
								for z in range(r + 1):
									if z & 1 == 1:
										print(j + 1, end=' ')
									else:
										print(i + 1, end=' ')
								for z in range(r):
									if z & 1 == 1:
										print(j + 1, end=' ')
									else:
										print(k + 1, end=' ')
							else:
								r = m // 2
								for z in range(r + 1):
									if z & 1 == 1:
										print(k + 1, end=' ')
									else:
										print(j + 1, end=' ')
								for z in range(r):
									if z & 1 == 1:
										print(j + 1, end=' ')
									else:
										print(i + 1, end=' ')
							print()
							flag = True
							break
				if flag:
					break
			if flag:
				break
		else:
			print('NO')


import sys
import math
from itertools import permutations

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod
for _ in range(II()):
	(n, m) = MI()
	l = []
	boo = False
	for i in range(n):
		l.append(list(SI()))
	for i in range(n):
		for j in range(n):
			if i != j and l[i][j] == l[j][i]:
				print('YES')
				ans = ([i + 1, j + 1] * m)[:m + 1]
				print(*ans)
				boo = True
				break
		if boo:
			break
	if boo:
		continue
	if m % 2:
		print('YES')
		ans = ([1, 2] * m)[:m + 1]
		print(*ans)
		continue
	if n == 2:
		print('NO')
		continue
	for c in permutations(range(3), 3):
		(i, j, k) = c
		if l[i][j] == l[j][k]:
			break
	print('YES')
	ans = ([i + 1, j + 1] * (m // 2))[:m // 2][::-1] + [j + 1] + ([k + 1, j + 1] * (m // 2))[:m // 2]
	print(*ans)


import sys
from collections import defaultdict
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	graph = []
	for i in range(n):
		row = input().rstrip()
		graph.append(list(row))
	canGoToA = defaultdict(list)
	hasSame = -1
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if graph[i][j] == 'a':
				canGoToA[i].append(j)
			if graph[i][j] == graph[j][i]:
				hasSame = (i, j)
	result = []
	possible = True
	if m % 2 != 0:
		for i in range(m + 1):
			if i % 2 == 0:
				result.append(1)
			else:
				result.append(2)
	elif hasSame != -1:
		for i in range(m + 1):
			if i % 2 == 0:
				result.append(hasSame[0] + 1)
			else:
				result.append(hasSame[1] + 1)
	else:
		flag = False
		for i in range(n):
			if flag:
				break
			for j in range(n):
				if i == j:
					continue
				if graph[i][j] == 'a' and len(canGoToA[j]) != 0:
					z = canGoToA[j][0]
					flag = True
					if m // 2 % 2 == 1:
						order = [i + 1, j + 1, z + 1, j + 1]
						for k in range(m + 1):
							result.append(order[k % 4])
					else:
						result.append(j + 1)
						order = [i + 1, j + 1, z + 1, j + 1]
						for k in range(m):
							result.append(order[k % 4])
					break
		if not flag:
			possible = False
	if possible:
		print('YES')
		print(*result)
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m % 2 == 1:
		for i in range(n):
			s = input()
		print('YES')
		for i in range(m + 1):
			print(i % 2 + 1, end=' ')
		print()
	else:
		A = []
		for i in range(n):
			B = input()
			A.append(B)
		(k1, k2) = (-1, -1)
		for i in range(n):
			for j in range(i):
				if A[i][j] == A[j][i]:
					(k1, k2) = (i, j)
					break
			if k1 != -1:
				break
		if k1 == -1:
			if n == 2:
				print('NO')
			else:
				(x, y, z) = (-1, -1, -1)
				if A[0][1] == A[0][2]:
					x = 1
					if A[1][2] == A[0][1]:
						y = 2
						z = 3
					else:
						z = 2
						y = 3
				elif A[1][0] == A[1][2]:
					x = 2
					if A[0][2] == A[1][0]:
						y = 1
						z = 3
					else:
						z = 3
						y = 1
				else:
					x = 3
					if A[0][1] == A[2][0]:
						y = 1
						z = 2
					else:
						z = 2
						y = 1
				if m % 4 == 2:
					print('YES')
					print(x, end=' ')
					for i in range(m // 4):
						print(y, x, end=' ')
					print(y, z, end=' ')
					for i in range(m // 4):
						print(y, z, end=' ')
					print()
				else:
					print('YES')
					print(y, x, end=' ')
					for i in range(m // 4 - 1):
						print(y, x, end=' ')
					print(y, end=' ')
					for i in range(m // 4):
						print(z, y, end=' ')
					print()
		else:
			print('YES')
			for i in range(m + 1):
				if i % 2 == 0:
					print(k1 + 1, end=' ')
				else:
					print(k2 + 1, end=' ')
			print()


def main():
	T = int(input())
	for _ in range(T):
		(n, m) = input().strip().split()
		(n, m) = (int(n), int(m))
		graph = []
		s = ''
		for i in range(n):
			s = input()
			graph.append(s)
		if m % 2 == 1:
			print('YES')
			for i in range(m + 1):
				print(i % 2 + 1, end=' ')
			print()
			continue
		else:
			find_el = False
			loop = []
			for i in range(n):
				if find_el:
					break
				for j in range(i + 1, n):
					if graph[i][j] == graph[j][i]:
						loop = [i, j]
						find_el = True
						break
			if find_el:
				print('YES')
				for i in range(m + 1):
					print(loop[i % 2] + 1, end=' ')
				print()
				continue
			find_c = False
			cl = []
			for i in range(n):
				if find_c:
					break
				for j in range(n):
					if find_c:
						break
					if i != j:
						for k in range(n):
							if i != k and j != k:
								if graph[i][j] == graph[j][k] and graph[k][j] == graph[j][i]:
									cl = [i, j, k]
									find_c = True
									break
			if find_c:
				ans = [0 for i in range(m + 3)]
				cur = 0
				while cur < m + 3:
					ans[cur] = cl[1]
					cur += 2
				cur = 1
				while cur < m + 3:
					ans[cur] = cl[0]
					cur += 4
				cur = 3
				while cur < m + 3:
					ans[cur] = cl[2]
					cur += 4
				if m % 4 == 2:
					ans = ans[1:]
				print('YES')
				for i in range(m + 1):
					print(ans[i] + 1, end=' ')
				print()
				continue
			print('NO')
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
for f in range(int(input())):
	(n, m) = map(int, input().split())
	e = []
	for i in range(n):
		e.append(input())
	if n == 2:
		if m % 2:
			print('YES')
			print(*[1, 2] * (m // 2 + 1))
		elif e[0][1] == e[1][0]:
			print('YES')
			print(*[1, 2] * (m // 2) + [1])
		else:
			print('NO')
	elif m % 2:
		print('YES')
		print(*[1, 2] * (m // 2 + 1))
	else:
		good = False
		for i in range(2):
			for j in range(i + 1, 3):
				if e[i][j] == e[j][i]:
					good = True
					gi = i + 1
					gj = j + 1
		if good:
			print('YES')
			print(*[gi, gj] * (m // 2) + [gi])
		else:
			for i in range(3):
				for j in range(3):
					if j != i:
						for k in range(3):
							if k != i and k != j and (e[i][j] == e[j][k]):
								gi = i + 1
								gj = j + 1
								gk = k + 1
			print('YES')
			if m % 4 == 2:
				print(*[gi] + [gj, gk, gj, gi] * (m // 4) + [gj, gk])
			else:
				print(*[gj, gk, gj, gi] * (m // 4) + [gj])


from sys import stdin, stdout
from collections import defaultdict

def main():
	t = int(stdin.readline())
	for _ in range(t):
		(n, m) = list(map(int, stdin.readline().split()))
		s = []
		for _ in range(n):
			s.append(stdin.readline().strip())
		if m % 2 == 1:
			ans = ['1', '2']
			for _ in range(0, m - 1, 2):
				ans.append('1')
				ans.append('2')
			stdout.write('YES\n')
			stdout.write(' '.join(ans) + '\n')
			continue
		if n == 2 and s[0][1] != s[1][0]:
			stdout.write('NO\n')
			continue
		is_found = False
		for i in range(n):
			for j in range(n):
				if i == j:
					continue
				if s[i][j] == s[j][i]:
					ans = [str(i + 1)]
					for _ in range(0, m - 1, 2):
						ans.append(str(j + 1))
						ans.append(str(i + 1))
					stdout.write('YES\n')
					stdout.write(' '.join(ans) + '\n')
					is_found = True
					break
			if is_found:
				break
		if is_found:
			continue
		ans = []
		for i in range(n):
			has_a = -1
			has_b = -1
			for j in range(n):
				if i == j:
					continue
				if s[i][j] == 'a':
					has_a = j
				elif s[i][j] == 'b':
					has_b = j
			if has_a != -1 and has_b != -1:
				ans = [has_b, i, has_a]
				break
		if ans:
			if int(m / 2) % 2 == 1:
				pos = 0
			else:
				pos = 1
			is_up = 1
			answer = []
			while len(answer) <= m:
				answer.append(str(ans[pos] + 1))
				pos += is_up
				if pos == 3:
					pos = 1
					is_up = -1
				elif pos == -1:
					pos = 1
					is_up = 1
			stdout.write('YES\n')
			stdout.write(' '.join(answer) + '\n')
		else:
			stdout.write('NO\n')
main()


for nt in range(int(input())):
	(n, m) = map(int, input().split())
	edge = []
	for i in range(n):
		edge.append(list(input()))
	found = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if edge[i][j] == edge[j][i]:
				found = [i, j]
	if found:
		print('YES')
		j = 0
		for i in range(m):
			print(found[j] + 1, end=' ')
			j = 1 - j
		print(found[j] + 1)
		continue
	if m % 2:
		print('YES')
		for i in range(m + 1):
			print(i % 2 + 1, end=' ')
		print()
		continue
	if n == 2:
		print('NO')
		continue
	print('YES')
	if m == 2:
		if edge[0][1] == edge[1][2]:
			ans = [1, 2, 3]
		elif edge[1][2] == edge[2][0]:
			ans = [2, 3, 1]
		elif edge[2][0] == edge[0][1]:
			ans = [3, 1, 2]
		print(*ans)
		continue
	if edge[0][1] == edge[1][2]:
		(i, j, k) = (1, 2, 3)
	elif edge[1][2] == edge[2][0]:
		(i, j, k) = (2, 3, 1)
	else:
		(i, j, k) = (3, 1, 2)
	if m % 4:
		print(*[i] + [j, i] * (m // 4) + [j, k] * (m // 4 + 1))
	else:
		print(*[j, i] * (m // 4) + [j, k] * (m // 4) + [j])


T = int(input())
for t in range(T):
	(n, m) = tuple([int(x) for x in input().split()])
	ss = []
	for i in range(n):
		ss.append(input().strip())
	if n == 2:
		if ss[0][1] != ss[1][0] and m % 2 == 0:
			print('NO')
		else:
			print('YES')
			print(' '.join([str(i % 2 + 1) for i in range(m + 1)]))
	else:
		print('YES')
		two_nodes = None
		for i in range(n):
			for j in range(i + 1, n):
				if ss[i][j] == ss[j][i]:
					two_nodes = (i, j)
					break
			if two_nodes is not None:
				break
		if two_nodes is not None:
			solution = [str(two_nodes[i % 2] + 1) for i in range(m + 1)]
			print(' '.join(solution))
			continue
		same_label_pos = []
		for i in range(3):
			if ss[i][(i + 1) % 3] == ss[i][(i + 2) % 3]:
				same_label_pos.append(i)
		if len(same_label_pos) == 0:
			solution = [str(i % 3 + 1) for i in range(m + 1)]
			print(' '.join(solution))
			continue
		elif m % 2 == 1:
			solution = [str(i % 2 + 1) for i in range(m + 1)]
			print(' '.join(solution))
			continue
		else:
			diff_label_pos = None
			for i in range(3):
				if i in same_label_pos:
					continue
				else:
					diff_label_pos = i
					break
			solution = [str(same_label_pos[i % 2] + 1) for i in range(m // 2)] + [str(diff_label_pos + 1)] + [str(same_label_pos[(i + m // 2 % 2) % 2] + 1) for i in range(m // 2)]
			print(' '.join(solution))
			continue


def main():
	num_cases = int(input())
	for case_num in range(1, num_cases + 1):
		solve(case_num)

def solve(case_num):
	(n, m) = [int(x) for x in input().split()]
	A = [input() for _ in range(n)]
	if m % 2 != 0:
		cycle = [1, 2]
		print('YES')
		print(' '.join((str(cycle[i % 2]) for i in range(m + 1))))
		return
	if n == 2:
		if A[0][1] == A[1][0]:
			cycle = [1, 2]
			print('YES')
			print(' '.join((str(cycle[i % 2]) for i in range(m + 1))))
		else:
			print('NO')
		return
	for i in range(3):
		j = (i + 1) % 3
		if A[i][j] == A[j][i]:
			cycle = [i + 1, j + 1]
			print('YES')
			print(' '.join((str(cycle[i % 2]) for i in range(m + 1))))
			return
	if A[0][1] == A[1][2] == A[2][0]:
		cycle = [1, 2, 3]
		print('YES')
		print(' '.join((str(cycle[i % 3]) for i in range(m + 1))))
		return
	for i in range(3):
		j = (i + 1) % 3
		k = (j + 1) % 3
		if A[i][j] == A[j][k]:
			if m % 4 == 0:
				first = [j + 1, k + 1] * (m // 4)
				mid = [j + 1]
				second = [i + 1, j + 1] * (m // 4)
			else:
				first = [i + 1, j + 1] * ((m - 2) // 4)
				mid = [i + 1, j + 1, k + 1]
				second = [j + 1, k + 1] * ((m - 2) // 4)
			path = first + mid + second
			print('YES')
			print(' '.join((str(x) for x in path)))
			return
main()


def get_best_edge(graph):
	for i in range(len(graph) - 1):
		for j in range(i + 1, len(graph)):
			if graph[i][j] == graph[j][i]:
				return (True, i, j)
	return (False, 0, 1, 2)

def solve(graph, m):
	x = get_best_edge(graph)
	res = []
	if x[0] or m % 2 == 1:
		for i in range(m + 1):
			if i % 2 == 0:
				res.append(str(x[1] + 1))
			else:
				res.append(str(x[2] + 1))
		return res
	if len(graph) == 2:
		return res
	return solve_on_first3(graph, m)

def check_short_cycle(graph):
	if graph[0][:3] == '*ba' and graph[1][:3] == 'a*b':
		return True
	if graph[0][:3] == '*ab' and graph[1][:3] == 'b*a':
		return True
	return False

def get_three_nodes(graph):
	if graph[0][1] != graph[0][2]:
		return (2, 0, 1)
	if graph[1][0] != graph[1][2]:
		return (0, 1, 2)
	if graph[2][0] != graph[2][1]:
		return (0, 2, 1)

def solve_on_first3(graph, m):
	res = []
	if check_short_cycle(graph):
		for i in range(m + 1):
			res.append(str(i % 3 + 1))
		return res
	(x, y, z) = get_three_nodes(graph)
	if m // 2 % 2 == 1:
		for i in range(m + 1):
			if i % 4 == 0:
				res.append(str(x + 1))
			elif i % 4 == 1:
				res.append(str(y + 1))
			elif i % 4 == 2:
				res.append(str(z + 1))
			elif i % 4 == 3:
				res.append(str(y + 1))
	else:
		for i in range(m + 1):
			if i % 4 == 0:
				res.append(str(y + 1))
			elif i % 4 == 1:
				res.append(str(z + 1))
			elif i % 4 == 2:
				res.append(str(y + 1))
			elif i % 4 == 3:
				res.append(str(x + 1))
	return res
T = int(input())
for _ in range(T):
	(n, m) = tuple(map(int, input().split(' ')))
	graph = []
	for i in range(n):
		graph.append(input())
	answer = solve(graph, m)
	if len(answer) > 0:
		print('YES')
		print(' '.join(answer))
	else:
		print('NO')


import sys, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def solve_(arr, m):
	if m % 2 == 1:
		return [0, 1] * ((m + 1) // 2)
	for (i, row) in enumerate(arr):
		for (j, cell) in enumerate(row[:i]):
			if cell == arr[j][i]:
				return [i, j] * (m // 2) + [i]
	(x, y, z) = (-1, -1, -1)
	for (i, row) in enumerate(arr):
		c = Counter(row)
		if c['a'] and c['b']:
			x = row.index('a')
			y = row.index('b')
			z = i
			break
	else:
		if len(arr) > 2:
			log('error')
		return []
	log(x, y, z)
	if m % 4 == 0:
		return [z, x, z, y] * (m // 4) + [z]
	if m % 4 == 2:
		return [y, z] * (m // 4) + [x, z, y] + [z, x] * (m // 4)
	return []
for case_num in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = read_strings(n)
	res = solve(arr, m)
	res = [1 + x for x in res]
	if res:
		assert len(res) == m + 1
		print('YES')
		print(*res)
	else:
		print('NO')


import sys
import math
from collections import defaultdict, Counter, deque
sys.setrecursionlimit(10 ** 4)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	d = [[0] * n for j in range(n)]
	flag = 0
	ans = [0, 0]
	for j in range(n):
		s = input()
		for k in range(n):
			if j != k:
				d[j][k] = s[k]
				if d[j][k] == d[k][j]:
					flag = 1
					ans = [j + 1, k + 1]
	if flag:
		print('YES')
		for j in range(m + 1):
			print(ans[j % 2], end=' ')
		print()
		continue
	if m & 1:
		ans = [1, 2]
		print('YES')
		for j in range(m + 1):
			print(ans[j % 2], end=' ')
		print()
	elif n == 2:
		print('NO')
	else:
		print('YES')
		if d[0][1] == d[1][2]:
			ans = [1, 2, 3]
		elif d[2][0] == d[1][2]:
			ans = [2, 3, 1]
		else:
			ans = [3, 1, 2]
		n1 = m // 2
		if n1 & 1:
			for j in range(n1 + 1):
				print(ans[j % 2], end=' ')
			ans[0] = ans[2]
			for j in range(n1):
				print(ans[j % 2], end=' ')
		else:
			ans1 = ans[:]
			ans1[0] = ans1[1]
			ans1[1] = ans1[2]
			for j in range(n1 + 1):
				print(ans1[j % 2], end=' ')
			for j in range(n1):
				print(ans[j % 2], end=' ')
		print()


import sys
input = sys.stdin.readline
for t in range(int(input())):
	(N, M) = map(int, input().split())
	S = [input() for i in range(N)]
	F = 0
	for i in range(N):
		for j in range(N):
			if i != j and S[i][j] == S[j][i]:
				F = 1
				P = [i + 1]
				for k in range(M):
					if k & 1:
						P.append(i + 1)
					else:
						P.append(j + 1)
				print('YES')
				print(*P)
				break
		if F:
			break
	if F:
		continue
	X = [[[-1, -1], [-1, -1]] for i in range(N)]
	for i in range(N):
		for j in range(N):
			if i != j:
				if S[i][j] == 'a':
					X[i][0][1] = j
					X[j][0][0] = i
				else:
					X[j][1][1] = j
					X[i][1][0] = i
	if M & 1:
		P = [(i & 1) + 1 for i in range(M + 1)]
		print('YES')
		print(*P)
		continue
	F = 0
	for i in range(N):
		for j in range(2):
			if min(X[i][j]) >= 0:
				P = [0] * (M + 1)
				P[M >> 1] = i + 1
				for k in range(M >> 1):
					if k & 1:
						P[(M >> 1) - k - 1] = i + 1
						P[(M >> 1) + k + 1] = i + 1
					else:
						P[(M >> 1) - k - 1] = X[i][j][0] + 1
						P[(M >> 1) + k + 1] = X[i][j][1] + 1
				print('YES')
				print(*P)
				F = 1
				break
		if F:
			break
	if F:
		continue
	print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = [input() for i in range(n)]
	if m % 2 == 1:
		print('YES')
		print('1 2 ' * (m // 2 + 1))
		continue
	ans = []
	for v in range(n):
		for u1 in range(n):
			for u2 in range(n):
				if v != u1 and v != u2 and (g[v][u1] == g[u2][v]) and (g[u1][v] == g[v][u2]):
					ans = ([u1 + 1, v + 1] * m)[:m // 2][::-1] + [v + 1] + ([u2 + 1, v + 1] * m)[:m // 2]
					break
			else:
				continue
			break
		else:
			continue
		break
	if len(ans) > 0:
		print('YES')
		print(*ans)
		continue
	print('NO')


from collections import defaultdict
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	adj = [['*' for k in range(n + 1)] for j in range(n + 1)]
	for j in range(n):
		s = input()
		for k in range(n):
			adj[j + 1][k + 1] = s[k]
	poss = 0
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			if j != k and adj[j][k] == adj[k][j]:
				poss = 1
				ind = []
				for u in range(m + 1):
					if u % 2 == 0:
						ind.append(j)
					else:
						ind.append(k)
				break
		if poss:
			break
	if poss:
		print('YES')
		print(*ind)
	elif m % 2 != 0:
		ind = []
		for j in range(m + 1):
			if j % 2 == 0:
				ind.append(1)
			else:
				ind.append(2)
		print('YES')
		print(*ind)
	else:
		for j in range(1, n + 1):
			ind = []
			ine = defaultdict(lambda : [])
			out = defaultdict(lambda : [])
			for k in range(1, n + 1):
				if j != k:
					ine[adj[k][j]].append(k)
					out[adj[j][k]].append(k)
			if ine['a'] != [] and out['a'] != [] and (ine['a'][-1] == out['a'][-1]):
				out['a'].pop()
			if ine['b'] != [] and out['b'] != [] and (ine['b'][-1] == out['b'][-1]):
				out['b'].pop()
			if ine['a'] != [] and out['a'] != []:
				poss = 1
				q1 = []
				q2 = []
				for k in range(m // 2 + 1):
					if k % 2 == 0:
						q1.append(j)
					else:
						q1.append(ine['a'][-1])
				for k in range(m // 2):
					if k % 2 == 0:
						q2.append(out['a'][-1])
					else:
						q2.append(j)
				ind = q1[::-1] + q2
			if ine['b'] != [] and out['b'] != []:
				poss = 1
				q1 = []
				q2 = []
				for k in range(m // 2 + 1):
					if k % 2 == 0:
						q1.append(j)
					else:
						q1.append(ine['b'][-1])
				for k in range(m // 2):
					if k % 2 == 0:
						q2.append(out['b'][-1])
					else:
						q2.append(j)
				ind = q1[::-1] + q2
			if poss:
				break
		if poss:
			print('YES')
			print(*ind)
		else:
			print('NO')


from itertools import chain, cycle, islice
from sys import stdin
readline = stdin.readline

def read_ints():
	return map(int, readline().split())

def read_string():
	return readline()[:-1]

def f(graph, m):
	assert n >= 2
	assert m >= 1
	for u in range(n):
		for v in range(u + 1, n):
			if graph[u][v] == graph[v][u]:
				return islice(cycle([u, v]), m + 1)
	if m % 2 != 0:
		return islice(cycle([0, 1]), m + 1)
	g = [('a' in row, 'b' in row) for row in graph]
	for u in range(n):
		for v in range(n):
			if u == v:
				continue
			ch = graph[u][v]
			if g[v][ord(ch) - ord('a')]:
				w = graph[v].index(ch)
				base = [u, v, w]
				v_need = m + 1 - 3
				v_per_half = v_need // 2
				fst_half = list(islice(cycle([v, u]), v_per_half))[::-1]
				snd_half = islice(cycle([v, w]), v_per_half)
				return chain(fst_half, base, snd_half)
	raise ValueError
(t_n,) = read_ints()
for i_t in range(t_n):
	(n, m) = read_ints()
	graph = [read_string() for i_row in range(n)]
	try:
		path = tuple(f(graph, m))
	except ValueError:
		print('NO')
	else:
		print('YES')
		print(*[v + 1 for v in path])


import sys
readline = sys.stdin.readline
from collections import deque
T = int(readline())
Ans = []
INF = 10 ** 9 + 7
for qu in range(T):
	(N, M) = map(int, readline().split())
	E = [[1 if s == 'a' else 0 for s in readline().strip()] for _ in range(N)]
	res = []
	for i in range(N):
		for j in range(N):
			if i == j:
				E[i][i] = None
			elif E[i][j] == E[j][i]:
				res = [i + 1, j + 1]
				break
		else:
			continue
		break
	if res:
		Ans.append('YES')
		Ans.append(' '.join(map(str, (res * (M // 2 + 5))[:M + 1])))
	elif M & 1:
		Ans.append('YES')
		Ans.append(' '.join(map(str, [1, 2] * (M // 2 + 1))))
	elif N == 2:
		Ans.append('NO')
	else:
		Ans.append('YES')
		if E[0][1] == E[1][2]:
			(x, y, z) = (1, 2, 3)
		elif E[1][2] == E[2][0]:
			(x, y, z) = (2, 3, 1)
		else:
			(x, y, z) = (3, 1, 2)
		ans = deque([x, y, z])
		M -= 2
		par = 0
		while M:
			M -= 2
			ans.appendleft([y, x][par])
			ans.append([y, z][par])
			par ^= 1
		Ans.append(' '.join(map(str, ans)))
print('\n'.join(Ans))


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(op) for op in input().split()]
	mt = [input() for i in range(n)]
	if m % 2 == 1:
		print('YES')
		for i in range(m + 1):
			print(1, end=' ') if i % 2 == 0 else print(2, end=' ')
		print()
	else:
		flag = False
		f2 = False
		for i in range(n):
			j = i + 1
			while j < n:
				if mt[i][j] == mt[j][i]:
					flag = True
					(a, b) = (i + 1, j + 1)
					break
				j += 1
		f2 = False
		if not flag:
			for i in range(n):
				if 'a' in mt[i] and 'b' in mt[i]:
					f2 = True
					(a, b, c) = (mt[i].find('a') + 1, mt[i].find('b') + 1, i + 1)
					break
		if flag:
			print('YES')
			for i in range(m + 1):
				print(a, end=' ') if i % 2 == 0 else print(b, end=' ')
			print()
		elif f2:
			print('YES')
			if int(m / 2) % 2 == 1:
				for i in range(int(m / 2)):
					print(a, end=' ') if i % 2 == 0 else print(c, end=' ')
				for i in range(int(m / 2) + 1):
					print(c, end=' ') if i % 2 == 0 else print(b, end=' ')
			else:
				for i in range(int(m / 2)):
					print(c, end=' ') if i % 2 == 0 else print(b, end=' ')
				for i in range(int(m / 2) + 1):
					print(c, end=' ') if i % 2 == 0 else print(a, end=' ')
			print()
		else:
			print('NO')


def find():
	(n, m) = map(int, input().split())
	g = []
	has = []
	for j in range(n):
		tmp = []
		tmp1 = [-1] * 2
		for (p, k) in enumerate(input()):
			tmp.append(k)
			if k != '*':
				tmp1[ord(k) - ord('a')] = p
		g.append(tmp)
		has.append(tmp1)
	if m % 2 != 0:
		ans = ' '.join([str(j % 2 + 1) for j in range(m + 1)])
		return 'Yes\n' + ans
	for j in range(n):
		for k in range(j + 1, n):
			if g[k][j] == g[j][k]:
				res = (j + 1, k + 1)
				ans = ' '.join([str(res[p % 2]) for p in range(m + 1)])
				return 'Yes\n' + ans
	for j in range(n):
		for k in range(n):
			if g[j][k] != '*' and has[k][ord(g[j][k]) - ord('a')] != -1:
				x = j + 1
				y = k + 1
				z = has[k][ord(g[j][k]) - ord('a')] + 1
				res = (x, y, z, y)
				dif = 0 if m // 2 % 2 != 0 else 1
				ans = ' '.join([str(res[(p + dif) % 4]) for p in range(m + 1)])
				return 'Yes\n' + ans
	return 'No'
for i in range(int(input())):
	print(find())


def main():
	t = int(input())
	allAns = []
	for _ in range(t):
		(n, m) = readIntArr()
		edges = []
		for __ in range(n):
			edges.append(input())
		ok = False
		if m % 2 == 1:
			ok = True
			ans = [0, 1] * ((m + 1) // 2)
		else:
			for i in range(n):
				for j in range(n):
					if i != j and edges[i][j] == edges[j][i]:
						ok = True
						ans = [i]
						currIsJ = True
						for __ in range(m):
							if currIsJ:
								ans.append(j)
							else:
								ans.append(i)
							currIsJ = not currIsJ
						break
				if ok:
					break
			if not ok:
				aOutIndexes = [[] for _ in range(n)]
				for i in range(n):
					for j in range(n):
						if edges[i][j] == 'a':
							aOutIndexes[i].append(j)
				for i in range(n):
					for j in aOutIndexes[i]:
						if len(aOutIndexes[j]) > 0:
							vertex1 = i
							vertex2 = j
							vertex3 = aOutIndexes[j][0]
							ok = True
							break
					if ok:
						break
				if ok:
					if m // 2 % 2 == 0:
						ans = [vertex2] + [vertex3, vertex2, vertex1, vertex2] * (m // 4)
					else:
						ans = [vertex1, vertex2, vertex3] + [vertex2, vertex1, vertex2, vertex3] * ((m - 2) // 4)
		if ok:
			allAns.append(['YES'])
			for i in range(len(ans)):
				ans[i] += 1
			allAns.append(ans)
		else:
			allAns.append(['NO'])
	multiLineArrayOfArraysPrint(allAns)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()


import sys

def input():
	return sys.stdin.readline().rstrip()

def slv():
	(n, m) = map(int, input().split())
	G = [[-1] * n for i in range(n)]
	for i in range(n):
		s = input()
		for j in range(n):
			if s[j] == 'b':
				G[i][j] = 1
			elif s[j] == 'a':
				G[i][j] = 0
	for i in range(n):
		for j in range(n):
			if G[i][j] == G[j][i] and G[i][j] >= 0:
				print('YES')
				ans = []
				for _ in range(m + 1):
					if _ % 2 == 0:
						ans.append(i + 1)
					else:
						ans.append(j + 1)
				print(*ans)
				return
	if m % 2 != 0:
		ans = []
		for _ in range(m + 1):
			if _ % 2 == 0:
				ans.append(1)
			else:
				ans.append(2)
		print('YES')
		print(*ans)
		return
	for y in range(n):
		lnode0 = []
		lnode1 = []
		rnode0 = []
		rnode1 = []
		for x in range(n):
			if G[x][y] == 0:
				lnode0.append(x)
			if G[x][y] == 1:
				lnode1.append(x)
			if G[y][x] == 0:
				rnode0.append(x)
			if G[y][x] == 1:
				rnode1.append(x)
		if lnode0 and rnode0:
			X = lnode0[0] + 1
			Y = y + 1
			Z = rnode0[0] + 1
			if m % 4 == 0:
				print('YES')
				ans = [Y, Z, Y, X] * (m // 4) + [Y]
				print(*ans)
			else:
				print('YES')
				ans = [X, Y, Z, Y] * (m // 4) + [X, Y, Z]
				print(*ans)
			return
		elif lnode1 and rnode1:
			X = lnode1[0] + 1
			Y = y + 1
			Z = rnode1[0] + 1
			if m % 4 == 0:
				print('YES')
				ans = [Y, Z, Y, X] * (m // 4) + [Y]
				print(*ans)
			else:
				print('YES')
				ans = [X, Y, Z, Y] * (m // 4) + [X, Y, Z]
				print(*ans)
			return
	print('NO')
	return

def main():
	t = int(input())
	for i in range(t):
		slv()
	return
main()


def print_ez(node1, node2, m):
	print('YES')
	p = []
	for i in range(m + 1):
		if i % 2:
			p.append(node2)
		else:
			p.append(node1)
	print(*p)

def print_hard(center, node1, node2, m):
	print('YES')
	p = [center]
	for i in range(m // 2):
		if i % 2:
			p.append(center)
		else:
			p.append(node1)
	for i in range(m // 2):
		if i % 2:
			p.append(center)
		else:
			p.append(node2)
	print(*p)

def print_another(center, node1, node2, m):
	print('YES')
	p = []
	for i in range(m // 2):
		if i % 2:
			p.append(center)
		else:
			p.append(node1)
	p.append(center)
	for i in range(m // 2):
		if i % 2:
			p.append(center)
		else:
			p.append(node2)
	print(*p)

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		l1 = input()
		l2 = input()
		if n != 2:
			l3 = input()
		for i in range(max(0, n - 3)):
			s = input()
		if n == 2:
			if l1[1] == l2[0]:
				print_ez(1, 2, m)
			elif m % 2:
				print_ez(1, 2, m)
			else:
				print('NO')
			continue
		if l1[1] == l2[0]:
			print_ez(1, 2, m)
		elif l1[2] == l3[0]:
			print_ez(1, 3, m)
		elif l2[2] == l3[1]:
			print_ez(2, 3, m)
		elif m % 2:
			print_ez(1, 2, m)
		elif m % 4:
			if l1[:3] != '*aa' and l1[:3] != '*bb':
				print_another(1, 2, 3, m)
			elif l2[:3] != 'a*a' and l2[:3] != 'b*b':
				print_another(2, 1, 3, m)
			else:
				print_another(3, 2, 1, m)
		elif l1[:3] != '*aa' and l1[:3] != '*bb':
			print_hard(1, 2, 3, m)
		elif l2[:3] != 'a*a' and l2[:3] != 'b*b':
			print_hard(2, 1, 3, m)
		else:
			print_hard(3, 1, 2, m)
main()


import sys
input = sys.stdin.readline

def find_aa_line(three):
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			for k in range(3):
				if j == k or i == k:
					continue
				if three[i][j] == three[j][k]:
					return [i + 1, j + 1, k + 1]
	return None

def find_aa_loop(three):
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			if three[i][j] == three[j][i]:
				return [i + 1, j + 1]
	return None
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	three = []
	for i in range(n):
		line = input().rstrip()
		if i < 3:
			three.append(line[:3])
	if n == 2:
		if m % 2 == 1:
			ans = [1 + item % 2 for item in range(m + 1)]
		elif three[0][1] == three[1][0]:
			ans = [1 + item % 2 for item in range(m + 1)]
		else:
			ans = None
	if n > 2:
		if m % 2 == 1:
			ans = [1 + item % 2 for item in range(m + 1)]
		else:
			uv = find_aa_loop(three)
			if uv is not None:
				ans = [uv[item % 2] for item in range(m + 1)]
			else:
				uvw = find_aa_line(three)
				if m % 4 == 0:
					module = [uvw[1], uvw[2], uvw[1], uvw[0]]
					ans = module * (m // 4) + [uvw[1]]
				else:
					module = [uvw[0], uvw[1], uvw[2], uvw[1]]
					ans = module * (m // 4) + [uvw[0], uvw[1], uvw[2]]
	if ans is not None:
		print('YES')
		print(*ans)
	else:
		print('NO')


import sys
for _ in range(int(input())):
	(n, t) = [int(x) for x in input().split()]
	arr = []
	for i in range(n):
		arr.append(input())
	if t % 2:
		print('YES')
		ans = []
		for i in range(t + 1):
			if i % 2:
				ans.append(2)
			else:
				ans.append(1)
		print(*ans)
		continue
	f = False
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i][j] == arr[j][i]:
				f = True
				ans = [i + 1, j + 1]
	if f:
		print('YES')
		print(*ans * (t // 2) + [ans[0]])
		continue
	for i in range(n):
		(ha, hb, va, vb) = (-1, -1, -1, -1)
		for k in range(n):
			if arr[k][i] == 'a':
				va = k
			if arr[k][i] == 'b':
				vb = k
			if arr[i][k] == 'a':
				ha = k
			if arr[i][k] == 'b':
				hb = k
		if ha != -1 and va != -1:
			f = True
			if t % 4 == 0:
				ans = [i + 1, ha + 1, i + 1, va + 1]
			else:
				ans = [ha + 1, i + 1, va + 1, i + 1]
			break
		if vb != -1 and hb != -1:
			f = True
			if t % 4 == 0:
				ans = [i + 1, vb + 1, i + 1, 1 + hb]
			else:
				ans = [hb + 1, i + 1, vb + 1, i + 1]
			break
	if f and t % 4 == 0:
		print('YES')
		res = []
		for i in range(t + 1):
			res.append(ans[i % 4])
		print(*res)
	elif f:
		print('YES')
		res = []
		for i in range(t + 1):
			res.append(ans[i % 4])
		print(*res)
	else:
		print('NO')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	(n, m) = map(int, input().split())
	graph1 = [[] for i in range(n + 1)]
	graph2 = [[] for i in range(n + 1)]
	rows = []
	for i in range(n):
		s = input()
		rows += [s]
		for j in range(n):
			if j == i:
				continue
			if s[j] == 'a':
				graph1[i] += [j]
			else:
				graph2[i] += [j]
	if m % 2:
		print('YES')
		ans = [1]
		for i in range(m):
			ans += [2 if i % 2 == 0 else 1]
		print(*ans)
		continue
	found = False
	for i in range(n):
		for j in range(i + 1, n):
			if rows[i][j] == rows[j][i]:
				found = True
				ans = [i + 1, j + 1]
				for i in range(m - 1):
					ans += [ans[i % 2]]
				print('YES')
				print(*ans)
				break
		if found:
			break
	if found:
		continue
	if n == 2:
		print('NO')
		continue
	found = False
	for p in range(3):
		for q in range(3):
			for r in range(3):
				if p == q:
					continue
				s = []
				nums = [p]
				while len(nums) != m // 2 + 1:
					nums += [q if nums[-1] == p else p]
				qq = nums[-1]
				if qq == r:
					continue
				while len(nums) != m + 1:
					nums += [r if nums[-1] == qq else qq]
				for i in range(m):
					s += [rows[nums[i]][nums[i + 1]]]
				if s == s[::-1]:
					found = True
					print('YES')
					print(*[i + 1 for i in nums])
			if found:
				break
		if found:
			break
	if found:
		continue
	if not found:
		print(0 / 0)


from sys import *
from math import ceil
ws = lambda : map(int, stdin.readline().strip().split())
li = lambda : list(map(int, stdin.readline().strip().split()))
mod = 1000000007

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def prod(l):
	ans = 1
	for i in range(len(l)):
		ans = ans * l[i]
	return ans

def sortindex(l, a):
	c = []
	if a == -1:
		rev = True
	else:
		rev = False
	for i in range(len(l)):
		c.append([l[i], i])
	x = sorted(c, reverse=rev)
	print(x)
	c = []
	for i in range(len(l)):
		c.append(x[i][1])
	return c
for _ in range(int(input())):
	(n, m) = ws()
	l = [-1] * n
	for i in range(n):
		l[i] = stdin.readline().strip()
	if n == 2:
		ans = [1, 2]
		if m & 1:
			print('YES')
			for i in range(m + 1):
				print(ans[i & 1], end=' ')
			print()
		elif l[0][1] == l[1][0]:
			print('YES')
			for i in range(m + 1):
				print(ans[i & 1], end=' ')
			print()
		else:
			print('NO')
	elif m == 1:
		print('YES')
		print('1 2')
	else:
		ans = 0
		for i in range(n):
			if ans != 0:
				break
			for j in range(n):
				if i == j:
					continue
				elif l[i][j] == l[j][i]:
					ans = (i + 1, j + 1)
					break
		if ans != 0:
			ans = [ans[0], ans[1]]
			print('YES')
			for i in range(m + 1):
				print(ans[i & 1], end=' ')
			print()
		else:
			print('YES')
			if m & 1:
				ans = [1, 2]
				for i in range(m + 1):
					print(ans[i & 1], end=' ')
				print()
			else:
				ans = 0
				flag = 0
				for i in range(n):
					if ans != 0:
						break
					if i != 0:
						flag = l[0][i]
					else:
						flag = l[1][i]
					for j in range(n):
						if i == j:
							continue
						if l[j][i] != flag:
							if i == 0:
								ans = [j + 1, i + 1, 2]
							else:
								ans = [j + 1, i + 1, 1]
							break
				if ans == 0:
					ans = [1, 2, 3]
				if m == 2:
					print(*ans)
				elif m // 2 & 1:
					flag = 0
					for i in range(m + 1):
						if i & 1 == 0:
							if flag & 1:
								print(ans[0], end=' ')
								flag -= 1
							else:
								print(ans[2], end=' ')
								flag += 1
						else:
							print(ans[1], end=' ')
					print()
				else:
					flag = 0
					for i in range(m + 1):
						if i & 1:
							if flag & 1:
								print(ans[0], end=' ')
								flag -= 1
							else:
								print(ans[2], end=' ')
								flag += 1
						else:
							print(ans[1], end=' ')
					print()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = [list(input().rstrip()) for _ in range(n)]
	if n == 2:
		if m % 2 or s[0][1] == s[1][0]:
			print('YES')
			ans = [i % 2 + 1 for i in range(m + 1)]
			print(*ans)
		else:
			print('NO')
		continue
	f = 0
	ans = []
	for i in range(n):
		for j in range(i + 1, n):
			if s[i][j] == s[j][i] or m % 2:
				f = 1
				ans = [i + 1 if k % 2 else j + 1 for k in range(m + 1)]
				break
		if f:
			break
	if not f:
		(a, b, c) = (s[0][1], s[1][2], s[2][0])
		if a == b == c:
			ans = [i % 3 + 1 for i in range(m + 1)]
		elif a == b:
			if not m % 4:
				s = 2
				c = 1
			else:
				s = 1
				c = 1
			ans = []
			for i in range(m + 1):
				ans.append(s)
				s += c
				if s == 3:
					c = -1
				if s == 1:
					c = 1
		elif b == c:
			if not m % 4:
				s = 3
				c = 1
			else:
				s = 2
				c = 1
			ans = []
			for i in range(m + 1):
				ans.append(s if s <= 3 else s % 3)
				s += c
				if s == 4:
					c = -1
				if s == 2:
					c = 1
		else:
			if not m % 4:
				s = 4
				c = 1
			else:
				s = 3
				c = 1
			ans = []
			for i in range(m + 1):
				ans.append(s if s <= 3 else s % 3)
				s += c
				if s == 5:
					c = -1
				if s == 3:
					c = 1
	print('YES')
	print(*ans)


import sys, io, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in2.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = input

	def debug(*args):
		pass

def solve():
	(n, m) = map(int, inp().split())
	E = [''] * (n * n)
	for i in range(n):
		for (j, c) in enumerate(inp().strip()):
			E[n * i + j] = c
	if m % 2:
		print('YES')
		print(*([1, 2] * m)[:m + 1])
		return
	for i in range(n):
		for j in range(i + 1, n):
			if E[n * i + j] == E[n * j + i]:
				print('YES')
				print(*([i + 1, j + 1] * m)[:m + 1])
				return
	for i in range(3):
		if i == 2 and n == 2:
			print('NO')
			return
		if 'a' in E[n * i:n * (i + 1)] and 'b' in E[n * i:n * (i + 1)]:
			j = k = 0
			while E[n * i + j] != 'a':
				j += 1
			while E[n * i + k] != 'b':
				k += 1
			if m % 4 == 0:
				print('YES')
				print(*[i + 1, j + 1] * (m // 4) + [i + 1, k + 1] * (m // 4) + [i + 1])
			else:
				print('YES')
				print(*[k + 1, i + 1] * (m // 4) + [k + 1, i + 1, j + 1] + [i + 1, j + 1] * (m // 4))
			return
	print('NO')
for _ in range(int(inp())):
	solve()


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, m) = ma()
	deg = [[] for i in range(n)]
	dma = {i: [] for i in range(n)}
	dmb = {i: [] for i in range(n)}
	for i in range(n):
		s = st()
		for j in range(n):
			deg[i].append(s[j])
			if s[j] == 'a':
				dma[i].append(j)
			elif s[j] == 'b':
				dmb[i].append(j)
	if m == 1:
		print('YES')
		print(1, 2)
		continue
	fl = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if deg[i][j] == deg[j][i]:
				fl = 1
				pos = i + 1
				pos2 = j + 1
				break
	if fl:
		print('YES')
		for i in range(m + 1):
			if i % 2:
				print(pos, end=' ')
			else:
				print(pos2, end=' ')
		print()
		continue
	if m % 2:
		print('YES')
		for i in range(m + 1):
			print(i % 2 + 1, end=' ')
		print()
		continue
	if n == 2:
		print('NO')
		continue
	else:
		if m // 2 % 2:
			ff = 0
			for i in range(n):
				for j in range(n):
					if i == j:
						continue
					ha = deg[i][j]
					if ha == 'a':
						if len(dma[j]):
							pos1 = i + 1
							pos2 = j + 1
							ll = 0
							for kk in dma[j]:
								if kk != pos1 - 1:
									pos3 = kk + 1
									ll = 1
									break
							if ll ^ 1:
								continue
							ff = 1
							break
					elif len(dmb[j]):
						pos1 = i + 1
						pos2 = j + 1
						ll = 0
						for kk in dmb[j]:
							if kk != pos1 - 1:
								pos3 = kk + 1
								ll = 1
								break
						if ll ^ 1:
							continue
						ff = 1
						break
				if ff:
					break
			if ff == 0:
				print('NO')
				continue
			print('YES')
			for i in range(m // 2 + 1):
				if i % 2 == 0:
					print(pos1, end=' ')
				else:
					print(pos2, end=' ')
			for i in range(m // 2):
				if i % 2:
					print(pos2, end=' ')
				else:
					print(pos3, end=' ')
		else:
			ff = 0
			for i in range(n):
				for j in range(n):
					if i == j:
						continue
					ha = deg[i][j]
					if ha == 'a':
						if len(dmb[i]):
							pos1 = i + 1
							pos2 = j + 1
							ll = 0
							for kk in dmb[i]:
								if kk != pos2 - 1:
									pos3 = kk + 1
									ll = 1
									break
							if ll ^ 1:
								continue
							ff = 1
							break
					elif len(dma[i]):
						pos1 = i + 1
						pos2 = j + 1
						ll = 0
						for kk in dma[i]:
							if kk != pos2 - 1:
								pos3 = kk + 1
								ll = 1
								break
						if ll ^ 1:
							continue
						ff = 1
						break
				if ff:
					break
			if ff == 0:
				print('NO')
				continue
			print('YES')
			for i in range(m // 2 + 1):
				if i % 2 == 0:
					print(pos1, end=' ')
				else:
					print(pos2, end=' ')
			for i in range(m // 2):
				if i % 2:
					print(pos1, end=' ')
				else:
					print(pos3, end=' ')
		print()


def arrIn():
	return list(map(int, input().split()))

def mapIn():
	return map(int, input().split())
for ii in range(int(input())):
	(n, k) = mapIn()
	arr = [[0] * n for i in range(n)]
	for i in range(n):
		s = input()
		for j in range(n):
			arr[i][j] = s[j]
	if k == 1:
		print('YES')
		print(1, 2)
		continue
	char = None
	flg1 = False
	flg2 = False
	for i in range(n):
		j2 = -1
		for j in range(n):
			if i != j:
				if arr[i][j] == arr[j][i]:
					char1 = arr[i][j]
					flg1 = True
					i1 = i + 1
					j1 = j + 1
					break
				elif j2 != -1 and arr[i][j] != arr[i][j2 - 1]:
					i1 = i + 1
					j1 = j + 1
					flg2 = True
					break
				elif j2 == -1:
					i1 = i + 1
					j2 = j + 1
		if flg1 or flg2:
			break
	if flg1 == True:
		print('YES')
		for i in range(k + 1):
			if i % 2 == 0:
				print(i1, end=' ')
			else:
				print(j1, end=' ')
		print()
	elif flg2 == True:
		print('YES')
		if k % 2 == 1:
			for i in range(k + 1):
				if i % 2 == 0:
					print(i1, end=' ')
				else:
					print(j2, end=' ')
			print()
		elif k // 2 % 2 == 1:
			for i in range(k + 1):
				if i % 4 == 0:
					print(j1, end=' ')
				elif i % 4 == 1:
					print(i1, end=' ')
				elif i % 4 == 2:
					print(j2, end=' ')
				else:
					print(i1, end=' ')
			print()
		else:
			for i in range(k + 1):
				if i % 4 == 0:
					print(i1, end=' ')
				elif i % 4 == 1:
					print(j1, end=' ')
				elif i % 4 == 2:
					print(i1, end=' ')
				else:
					print(j2, end=' ')
			print()
	elif k % 2 == 0:
		print('NO')
	else:
		print('YES')
		for i in range(k + 1):
			if i % 2 == 0:
				print(i1, end=' ')
			else:
				print(j2, end=' ')
		print()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	G = [input()[:-1] for _ in range(n)]
	if m % 2:
		ans = [1, 2] * (m // 2 + 1)
		print('YES')
		print(*ans)
		continue
	flag = 0
	for i in range(n):
		for j in range(i + 1, n):
			if G[i][j] == G[j][i]:
				ans = [i + 1, j + 1] * (m // 2) + [i + 1]
				flag = 1
				print('YES')
				print(*ans)
				break
		if flag:
			break
	else:
		dic = [{} for _ in range(n)]
		for i in range(n):
			for j in range(n):
				if i == j:
					continue
				dic[i][G[i][j]] = j
				if len(dic[i]) == 2:
					break
		flag = 0
		for i in range(n):
			for j in range(n):
				if i == j:
					continue
				if G[i][j] in dic[j]:
					k = dic[j][G[i][j]]
					m //= 2
					if not m % 2:
						ans = [j + 1] + [k + 1, j + 1, i + 1, j + 1] * (m // 2)
					else:
						ans = [i + 1] + [j + 1, k + 1, j + 1, i + 1] * (m // 2 + 1)
						ans = ans[:2 * m + 1]
					print('YES')
					print(*ans)
					flag = 1
					break
			if flag:
				break
		else:
			print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, m) = map(int, input().split())
	S = [input().strip() for i in range(n)]
	flag = 0
	for i in range(n):
		for j in range(i + 1, n):
			if S[i][j] == S[j][i]:
				ANSX = (i, j)
				flag = 1
				break
		if flag == 1:
			break
	if flag == 1:
		print('YES')
		ANS = []
		for i in range(m + 1):
			ANS.append(ANSX[i % 2] + 1)
		print(*ANS)
		continue
	if m % 2 == 1:
		print('YES')
		ANSX = (0, 1)
		ANS = []
		for i in range(m + 1):
			ANS.append(ANSX[i % 2] + 1)
		print(*ANS)
		continue
	if n == 2:
		print('NO')
		continue
	GO = [[0, 0] for i in range(n)]
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if S[i][j] == 'a':
				GO[i][0] = 1
			else:
				GO[i][1] = 1
	for i in range(n):
		if GO[i][0] == 1 and GO[i][1] == 1:
			USE = i
			break
	UA = -1
	UB = -1
	for i in range(n):
		if i == USE:
			continue
		if S[USE][i] == 'a':
			UA = i
		else:
			UB = i
	m2 = m // 2
	print('YES')
	if m2 % 2 == 0:
		ANS = []
		ANSX = (USE, UA)
		for i in range(m2 + 1):
			ANS.append(ANSX[i % 2] + 1)
		ANSX = (UB, USE)
		for i in range(m2):
			ANS.append(ANSX[i % 2] + 1)
		print(*ANS)
		continue
	else:
		ANS = []
		ANSX = (UA, USE)
		for i in range(m2 + 1):
			ANS.append(ANSX[i % 2] + 1)
		ANSX = (UB, USE)
		for i in range(m2):
			ANS.append(ANSX[i % 2] + 1)
		print(*ANS)
		continue


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	Edges = [input() for _ in range(n)]
	if m & 1:
		print('YES')
		L = [1 + (i & 1) for i in range(m + 1)]
		print(*L)
	else:
		flag = True
		for i in range(n - 1):
			for j in range(i + 1, n):
				if Edges[i][j] == Edges[j][i]:
					print('YES')
					L = [i + 1, j + 1] * (m // 2) + [i + 1]
					print(*L)
					flag = False
					break
			if not flag:
				break
		if flag:
			flag2 = False
			for i in range(n):
				S = set()
				E = Edges[i]
				a = ''
				for j in range(n):
					if i - j:
						if not a:
							a = E[j]
							J = j + 1
						elif E[j] != a:
							(I, K) = (i + 1, j + 1)
							flag2 = True
							break
				if flag2:
					break
			if flag2:
				print('YES')
				m //= 2
				L0 = [J, I, K, I] * (m // 4) + [J, I, K, I][:m % 4]
				L1 = [K, I, J, I] * (m // 4) + [K, I, J, I][:m % 4]
				L = L0[::-1] + [I] + L1
				print(*L)
			else:
				print('NO')


from itertools import cycle, islice

def solve():
	(n, m) = [int(t) for t in input().split()]
	g = [input() for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			if g[i][j] == g[j][i]:
				return repeat(i, j, m)
	if m % 2 == 1:
		return repeat(0, 1, m)
	if n >= 3:
		for (x, y, z) in ((0, 1, 2), (1, 2, 0), (2, 0, 1)):
			if g[x][y] == g[y][z]:
				if m // 2 % 2 == 1:
					return repeat(x, y, m // 2 - 1) + repeat(y, z, m // 2)
				else:
					return repeat(y, x, m // 2 - 1) + repeat(y, z, m // 2)
	return None

def repeat(i, j, k):
	return list(islice(cycle([i + 1, j + 1]), k + 1))
for _ in range(int(input())):
	res = solve()
	if res is None:
		print('NO')
	else:
		print('YES')
		print(*res)


def solveTestCase():
	nm = [int(i) for i in input().split()]
	G = []
	for i in range(nm[0]):
		G.append(input())
	if nm[1] % 2 == 1:
		print('YES')
		for i in range(nm[1] // 2 + 1):
			print('1 2', end=' ')
		print()
		return
	mypaire = (0, 0)
	for i in range(nm[0]):
		if mypaire[0] != 0:
			break
		for j in range(nm[0]):
			if i != j and G[i][j] == G[j][i]:
				mypaire = (i + 1, j + 1)
				break
	if mypaire[0] != 0:
		print('YES')
		for i in range(nm[1] // 2):
			print(str(mypaire[0]) + ' ' + str(mypaire[1]), end=' ')
		print(str(mypaire[0]))
		return
	mytriple = (0, 0, 0)
	for i in range(nm[0]):
		if mytriple[0] != 0:
			break
		for j in range(nm[0]):
			if mytriple[0] != 0:
				break
			if i == j:
				continue
			for k in range(nm[0]):
				if j == k or k == i:
					continue
				if G[i][j] == G[j][k]:
					mytriple = (i + 1, j + 1, k + 1)
					break
	if mytriple[0] != 0:
		print('YES')
		if nm[1] % 4 == 0:
			print(str(mytriple[1]), end=' ')
			for i in range(nm[1] // 2 - 1):
				print(mytriple[i % 2], end=' ')
		else:
			for i in range(nm[1] // 2):
				print(mytriple[i % 2], end=' ')
		print(str(mytriple[1]) + ' ' + str(mytriple[2]), end=' ')
		for i in range(nm[1] // 2 - 1):
			print(mytriple[i % 2 + 1], end=' ')
		print()
	else:
		print('NO')
t = int(input().split()[0])
while t > 0:
	t -= 1
	solveTestCase()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	x = []
	y = [-1, -1]
	for i in range(n):
		(a, b) = (0, 0)
		for j in range(n):
			if i != j:
				if l[i][j] == l[j][i]:
					x = [i + 1, j + 1]
					break
				if l[i][j] == 'a':
					a += 1
				if l[i][j] == 'b':
					b += 1
		if a == 0:
			y[1] = i
		if b == 0:
			y[0] = i
		if len(x):
			break
	if len(x):
		print('YES')
		l2 = x * ((m + 1) // 2)
		if m % 2 == 0:
			l2.append(x[0])
		print(*l2)
		continue
	if n == 2 and m % 2 == 0:
		print('NO')
		continue
	if m % 2:
		print('YES')
		l2 = [1, 2] * ((m + 1) // 2)
		print(*l2)
		continue
	if y[0] + 1 and y[1] + 1:
		x = 0
		for i in range(n):
			if i != y[0]:
				if l[i][y[1]] == 'a':
					x = i
					break
		if m // 2 % 2:
			l2 = [y[0] + 1, x + 1, y[1] + 1]
			c = 0
			for i in range((m - 2) // 2):
				if c:
					l2.append(x + 1)
					l2.append(y[1] + 1)
				else:
					l2.append(x + 1)
					l2.append(y[0] + 1)
				c ^= 1
		else:
			l2 = [y[0] + 1, y[1] + 1]
			c = 0
			for i in range((m - 2) // 2):
				if c:
					l2.append(x + 1)
					l2.append(y[1] + 1)
				else:
					l2.append(x + 1)
					l2.append(y[0] + 1)
				c ^= 1
			l2.append(y[1] + 1)
		print('YES')
		print(*l2)
		continue
	if y[1] + 1:
		l2 = [1]
		l3 = [0] * (n + 1)
		l3[1] = 1
		for i in range(n):
			if l[0][i] == 'b':
				x = i
				break
		while l3[x + 1] != 1:
			l2.append(x + 1)
			l3[x + 1] = 1
			for i in range(n):
				if l[x][i] == 'b':
					x = i
					break
		if x + 1 != 1:
			a = l2.index(x + 1)
			l2 = l2[a:]
		print('YES')
		if m < len(l2):
			print(*l2[:m + 1])
		else:
			ans = [l2[0]]
			for i in range(m):
				ans.append(l2[(i + 1) % len(l2)])
			print(*ans)
		continue
	l2 = [1]
	l3 = [0] * (n + 1)
	l3[1] = 1
	for i in range(n):
		if l[0][i] == 'a':
			x = i
			break
	while l3[x + 1] != 1:
		l2.append(x + 1)
		l3[x + 1] = 1
		for i in range(n):
			if l[x][i] == 'a':
				x = i
				break
	if x + 1 != 1:
		a = l2.index(x + 1)
		l2 = l2[a:]
	print('YES')
	if m < len(l2):
		print(*l2[:m + 1])
	else:
		ans = [l2[0]]
		for i in range(m):
			ans.append(l2[(i + 1) % len(l2)])
		print(*ans)


import sys

def read_ints():
	return [int(i) for i in sys.stdin.readline().strip().split()]

def read_int():
	return int(sys.stdin.readline().strip())

def check_and_output(lines, nodes):
	route = [lines[int(i) - 1][int(j) - 1] for (i, j) in zip(nodes[:-1], nodes[1:])]
	in_reverse = list(reversed(route))
	print('YES')
	print(' '.join(nodes))

def nodes_for_3graph(length, start, middle, end):
	return [start if (d + length // 2) % 2 else middle for d in range(length // 2 + 1)] + [middle if d % 2 else end for d in range(length // 2)]

def output_for_3graph(lines, length, start, middle, end):
	nodes = nodes_for_3graph(length, start, middle, end)
	check_and_output(lines, nodes)

def solve(n, length, lines):
	if length % 2 == 1:
		nodes = ['1' if d % 2 else '2' for d in range(length + 1)]
		check_and_output(lines, nodes)
		return
	for i in range(n):
		for j in range(n):
			if i != j and lines[i][j] == lines[j][i]:
				nodes = [str(i + 1 if d % 2 else j + 1) for d in range(length + 1)]
				check_and_output(lines, nodes)
				return
	if n == 2:
		print('NO')
		return
	if length == 2:
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if i != j and j != k and (i != k):
						if lines[i][j] == lines[j][k]:
							nodes = [str(i + 1), str(j + 1), str(k + 1)]
							check_and_output(lines, nodes)
							return
		print('NO')
		return
	if lines[0][1] == lines[1][2] == lines[2][0]:
		nodes = [str(d % 3 + 1) for d in range(length + 1)]
		check_and_output(lines, nodes)
		return
	if lines[0][2] == lines[2][1] == lines[1][0]:
		nodes = [str(3 - d % 3) for d in range(length + 1)]
		check_and_output(lines, nodes)
		return
	if lines[0][1] == lines[2][0]:
		output_for_3graph(lines, length, '2', '1', '3')
		return
	if lines[0][1] == lines[1][2]:
		output_for_3graph(lines, length, '1', '2', '3')
		return
	if lines[0][2] == lines[2][1]:
		output_for_3graph(lines, length, '1', '3', '2')
		return
ncases = read_int()
lines = []
for i in range(ncases):
	lines = []
	(n, length) = read_ints()
	skip = False
	for j in range(n):
		lines.append(sys.stdin.readline().strip())
	solve(n, length, lines)


from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	(n, m) = map(int, input().split())
	ll = []
	for _ in range(n):
		ll.append(input())
	if m % 2 == 1:
		print('YES')
		print('1 2 ' * ((m + 1) // 2))
		return
	if n == 2 and ll[0][1] != ll[1][0]:
		print('NO')
		return
	if ll[0][1] == ll[1][0]:
		print('YES')
		print('1 2 ' * (m // 2) + '1')
		return
	if ll[1][2] == ll[2][1]:
		print('YES')
		print('2 3 ' * (m // 2) + '2')
		return
	if ll[2][0] == ll[0][2]:
		print('YES')
		print('3 1 ' * (m // 2) + '3')
		return
	if ll[0][1] == ll[1][2]:
		print('YES')
		if m % 4 == 0:
			print('2 1 ' * (m // 4) + '2 3 ' * (m // 4) + '2')
		else:
			print('1 ' + '2 1 ' * (m // 4) + '2 3 ' * (m // 4) + '2 3')
		return
	if ll[1][2] == ll[2][0]:
		print('YES')
		if m % 4 == 0:
			print('3 2 ' * (m // 4) + '3 1 ' * (m // 4) + '3')
		else:
			print('2 ' + '3 2 ' * (m // 4) + '3 1 ' * (m // 4) + '3 1')
		return
	if ll[2][0] == ll[0][1]:
		print('YES')
		if m % 4 == 0:
			print('1 3 ' * (m // 4) + '1 2 ' * (m // 4) + '1')
		else:
			print('3 ' + '1 3 ' * (m // 4) + '1 2 ' * (m // 4) + '1 2')
		return

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def repeat(l, count):
	res = []
	for i in range(count):
		res.append(l[i % len(l)])
	return res

def solve(graph, l):
	if l % 2 == 1:
		return repeat([0, 1], l + 1)
	for i in range(len(graph)):
		for j in range(len(graph)):
			if i != j and graph[i][j] == graph[j][i]:
				return repeat([i, j], l + 1)
	if len(graph) == 2:
		return []
	for i in range(len(graph)):
		if 'a' not in graph[i] or 'b' not in graph[i]:
			continue
		to_a = [x for x in range(len(graph)) if graph[i][x] == 'a'][0]
		to_b = [x for x in range(len(graph)) if graph[i][x] == 'b'][0]
		if l % 4 == 0:
			return repeat([i, to_a, i, to_b], l + 1)
		for ch in 'ab':
			prev = [x for x in range(len(graph)) if graph[x][i] == ch]
			if not prev:
				continue
			prev = prev[0]
			return [prev] + repeat([i, to_a, i, to_b], l - 1) + [to_a if ch == 'a' else to_b]
	return []

def main():
	tests = int(input())
	for _ in range(tests):
		(n, l) = map(int, input().split())
		graph = [input() for _ in range(n)]
		res = solve(graph, l)
		if not res:
			print('NO')
		else:
			print('YES')
			for x in res:
				print(x + 1, end=' ')
			print()
main()


import sys
from sys import stdin

def solve(n, m, s):
	if m % 2 == 1:
		ans = [i % 2 + 1 for i in range(m + 1)]
		return ans
	for i in range(n):
		for j in range(i):
			if s[i][j] == s[j][i] and i != j:
				tmp = [i + 1, j + 1]
				ans = [tmp[x % 2] for x in range(m + 1)]
				return ans
	for i in range(n):
		ina = None
		outa = None
		for j in range(n):
			if s[j][i] == 'a':
				ina = j
				break
		for j in range(n):
			if s[i][j] == 'a':
				outa = j
				break
		if ina != None and outa != None:
			if m % 4 == 0:
				tmp = [i + 1, ina + 1, i + 1, outa + 1]
				ans = [tmp[x % 4] for x in range(m + 1)]
			else:
				tmp = [ina + 1, i + 1, outa + 1, i + 1]
				ans = [tmp[x % 4] for x in range(m + 1)]
			return ans
	else:
		return []

def pali(lis):
	for i in range(len(lis)):
		if lis[i] != lis[len(lis) - 1 - i]:
			return False
	return True
import random
mode = 0
tt = int(stdin.readline())
for loop in range(tt):
	if mode == 0:
		(n, m) = map(int, stdin.readline().split())
		s = [stdin.readline()[:-1] for i in range(n)]
	else:
		(n, m) = (random.randint(2, 10), random.randint(1, 20))
		tmp = ('a', 'b')
		s = [[tmp[random.randint(0, 1)] for i in range(n)] for j in range(n)]
		for i in range(n):
			s[i][i] = '*'
	cat = solve(n, m, s)
	if len(cat) == 0:
		print('NO')
	else:
		print('YES')
		print(*cat)


import sys
input = iter(sys.stdin.read().splitlines()).__next__

def solve():
	(n, m) = map(int, input().split())
	edges = [input() for _ in range(n)]
	if m % 2:
		path = [1, 2] * (m // 2 + 1)
		return f"YES\n{' '.join(map(str, path))}"
	for u in range(n):
		for v in range(u + 1, n):
			if edges[u][v] == edges[v][u]:
				path = [u + 1, v + 1] * (m // 2 + 1)
				return f"YES\n{' '.join(map(str, path[:m + 1]))}"
	incoming = [set() for _ in range(n)]
	outgoing = [set() for _ in range(n)]
	for u in range(n):
		for v in range(n):
			if u == v:
				continue
			incoming[u].add(edges[v][u])
			outgoing[u].add(edges[u][v])
	for u in range(n):
		in_and_out = incoming[u] & outgoing[u]
		if not in_and_out:
			continue
		char_needed = in_and_out.pop()
		for i in range(n):
			if edges[i][u] == char_needed:
				break
		o = edges[u].index(char_needed)
		needed_each_side = m // 2
		if needed_each_side % 2:
			path = [i, o] * (needed_each_side // 2)
			path.append(i)
			path.append(u)
			path.extend([o, i] * (needed_each_side // 2))
			path.append(o)
		else:
			left = [o, i] * (needed_each_side // 2)
			right = left.copy()
			path = left
			path.append(u)
			path.extend(right)
		return f"YES\n{' '.join(map(lambda vertex: str(vertex + 1), path))}"
	return 'NO'
t = int(input())
output = []
for _ in range(t):
	output.append(solve())
print(*output, sep='\n')


import sys
input = sys.stdin.readline
ansl = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sl = []
	for _ in range(n):
		sl.append(list(input()))
	if n == 2:
		if k % 2 == 1 or sl[0][1] == sl[1][0]:
			ansl.append([1, 2] * ((k - 1) // 2 + 1))
			if k % 2 == 0:
				ansl[-1].append(1)
		else:
			ansl.append([])
		continue
	ans = []
	if k % 2 == 1:
		ans.extend([1, 2] * (k // 2 + 1))
		ansl.append(ans)
		continue
	if sl[0][1] == sl[1][0]:
		ans.extend([1, 2] * (k // 2))
		ans.append(1)
		ansl.append(ans)
		continue
	if sl[1][2] == sl[2][1]:
		ans.extend([2, 3] * (k // 2))
		ans.append(2)
		ansl.append(ans)
		continue
	if sl[2][0] == sl[0][2]:
		ans.extend([3, 1] * (k // 2))
		ans.append(3)
		ansl.append(ans)
		continue
	if sl[0][1] == sl[1][2] and sl[1][2] == sl[2][0]:
		for i in range(k + 1):
			ans.append(i % 3 + 1)
		ansl.append(ans)
		continue
	abi = -1
	aai = -1
	bbi = -1
	for i in range(3):
		if sl[i][(i + 1) % 3] == 'a' and sl[i][(i + 2) % 3] == 'a':
			aai = i + 1
		elif sl[i][(i + 1) % 3] == 'b' and sl[i][(i + 2) % 3] == 'b':
			bbi = i + 1
		else:
			abi = i + 1
	if k % 4 == 0:
		ans.extend([abi, aai] * (k // 4))
		ans.extend([abi, bbi] * (k // 4))
		ans.append(abi)
	else:
		loop = k // 2 // 2 + 1
		ans.extend([aai, abi] * loop)
		ans.extend([bbi, abi] * loop)
		ans = ans[:-1]
	ansl.append(ans)
for row in ansl:
	if row:
		print('YES')
		print(*row)
	else:
		print('NO')


from itertools import permutations
import sys
input = lambda : sys.stdin.readline().rstrip()

def solve(n, m, graph):
	for i in range(n):
		for j in range(n):
			if i != j and graph[i][j] == graph[j][i]:
				print('YES')
				ans = ([i + 1, j + 1] * m)[:m + 1]
				print(*ans)
				return
	if m % 2:
		print('YES')
		ans = ([1, 2] * m)[:m + 1]
		print(*ans)
		return
	if n == 2:
		print('NO')
		return
	for c in permutations(range(3), 3):
		(i, j, k) = c
		if graph[i][j] == graph[j][k]:
			break
	print('YES')
	ans = ([i + 1, j + 1] * (m // 2))[:m // 2][::-1] + [j + 1] + ([k + 1, j + 1] * (m // 2))[:m // 2]
	print(*ans)
	return
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	graph = []
	for j in range(n):
		graph.append(input())
	solve(n, m, graph)


def find():
	(n, m) = map(int, input().split())
	g = [list(input()) for _ in range(n)]
	if m % 2 != 0:
		ans = ' '.join([str(j % 2 + 1) for j in range(m + 1)])
		return 'Yes\n' + ans
	for j in range(n):
		for k in range(j + 1, n):
			if g[k][j] == g[j][k]:
				res = (j + 1, k + 1)
				ans = ' '.join([str(res[p % 2]) for p in range(m + 1)])
				return 'Yes\n' + ans
	for j in range(n):
		last = []
		for k in range(n):
			last.append(g[k][j])
		last_set = set(last)
		for k in range(n):
			if g[j][k] != '*' and g[j][k] in last_set:
				x = last.index(g[j][k]) + 1
				y = j + 1
				z = k + 1
				res = (x, y, z, y)
				dif = 0 if m // 2 % 2 != 0 else 1
				ans = ' '.join([str(res[(p + dif) % 4]) for p in range(m + 1)])
				return 'Yes\n' + ans
	return 'No'
for i in range(int(input())):
	print(find())


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	(n, m) = R()
	s = [S() for i in range(n)]
	if n == 2 and m % 2 == 0 and (s[0][1] != s[1][0]):
		print('NO')
		continue
	flg = False
	AB = 0
	A = 0
	B = 0
	print('YES')
	v = [[0, 0] for i in range(n)]
	flg = False
	for i in range(n):
		for j in range(n):
			if s[i][j] == '*':
				continue
			if s[i][j] == s[j][i]:
				flg = [i + 1, j + 1]
			if s[i][j] == 'a':
				v[i][0] = j + 1
			else:
				v[i][1] = j + 1
		if v[i][0] and v[i][1]:
			AB = i + 1
		elif v[i][0]:
			A = i + 1
		else:
			B = i + 1
	if flg:
		for i in range(m + 1):
			print(flg[i % 2], end=' ')
		print()
	elif m % 2:
		for i in range(m + 1):
			print(2 - i % 2, end=' ')
		print()
	elif A and B:
		flg = [A, B]
		for i in range(m // 2):
			print(flg[i % 2], end=' ')
		print(AB, end=' ')
		flg = [B if m % 4 else A, AB]
		for i in range(m // 2):
			print(flg[i % 2], end=' ')
		print()
	elif B:
		flg = B
		for i in range(m + 1):
			print(flg, end=' ')
			flg = v[flg - 1][1]
		print()
	else:
		flg = v[0][0]
		for i in range(m + 1):
			print(flg, end=' ')
			flg = v[flg - 1][0]
		print()


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def dadd(d, p, val):
	if p in d:
		d[p].append(val)
	else:
		d[p] = [val]

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
uu = t
while t > 0:
	t -= 1
	(n, m) = mi()
	a = []
	for i in range(n):
		a.append(si())
	ide = [{} for i in range(n + 1)]
	ode = [{} for i in range(n + 1)]
	for i in range(n):
		for j in range(n):
			dadd(ode[i], a[i][j], j)
			dadd(ide[j], a[i][j], i)
	if m % 2:
		print('YES')
		ans = [1, 2] * ((m + 1) // 2)
		print(*ans)
		continue
	flag = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i][j] == a[j][i]:
				ans = [i + 1, j + 1] * (2 * m + 4)
				flag = 1
				break
		if flag:
			break
	if flag:
		print('YES')
		print(*ans[:m + 1])
		continue
	ans = []
	if m // 2 % 2:
		ans = []
		flag = 0
		for i in range(n):
			if flag:
				break
			for j in 'ab':
				if j in ide[i] and j in ode[i]:
					for u in range(m // 2 + 1):
						if u % 2 == 0:
							ans.append(ide[i][j][0] + 1)
						else:
							ans.append(i + 1)
					for u in range(m // 2):
						if u % 2 == 0:
							ans.append(ode[i][j][0] + 1)
						else:
							ans.append(i + 1)
					flag = 1
					break
		if len(ans):
			print('YES')
			print(*ans)
		else:
			print('NO')
	else:
		flag = 0
		for i in range(n):
			if flag:
				break
			if 'a' in ode[i] and 'b' in ode[i]:
				for u in range(m // 2 + 1):
					if u % 2:
						ans.append(ode[i]['a'][0] + 1)
					else:
						ans.append(i + 1)
				for u in range(m // 2):
					if u % 2 == 0:
						ans.append(ode[i]['b'][0] + 1)
					else:
						ans.append(i + 1)
				flag = 1
				break
		if len(ans):
			print('YES')
			print(*ans)
		else:
			print('NO')


import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
input = sys.stdin.readline
getS = lambda : input().strip()
getN = lambda : int(input())
getList = lambda : list(map(int, input().split()))
getZList = lambda : [int(x) - 1 for x in input().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
divide = lambda x: pow(x, MOD - 2, MOD)

def nck(n, k, kaijyo):
	return npk(n, k, kaijyo) * divide(kaijyo[k]) % MOD

def npk(n, k, kaijyo):
	if k == 0 or k == n:
		return n % MOD
	return kaijyo[n] * divide(kaijyo[n - k]) % MOD

def fact_and_inv(SIZE):
	inv = [0] * SIZE
	fac = [0] * SIZE
	finv = [0] * SIZE
	inv[1] = 1
	fac[0] = fac[1] = 1
	finv[0] = finv[1] = 1
	for i in range(2, SIZE):
		inv[i] = MOD - MOD // i * inv[MOD % i] % MOD
		fac[i] = fac[i - 1] * i % MOD
		finv[i] = finv[i - 1] * inv[i] % MOD
	return (fac, finv)

def renritsu(A, Y):
	A = np.matrix(A)
	Y = np.matrix(Y)
	Y = np.reshape(Y, (-1, 1))
	X = np.linalg.solve(A, Y)
	return X.flatten().tolist()[0]

class TwoDimGrid:

	def __init__(self, h, w, wall='#'):
		self.h = h
		self.w = w
		self.size = (h + 2) * (w + 2)
		self.wall = wall
		self.get_grid()

	def get_grid(self):
		grid = [self.wall * (self.w + 2)]
		for i in range(self.h):
			grid.append(self.wall + getS() + self.wall)
		grid.append(self.wall * (self.w + 2))
		self.grid = grid

	def init_cost(self):
		self.cost = [INF] * self.size

	def pos(self, x, y):
		return y * (self.w + 2) + x

	def getgrid(self, x, y):
		return self.grid[y][x]

	def get(self, x, y):
		return self.cost[self.pos(x, y)]

	def set(self, x, y, v):
		self.cost[self.pos(x, y)] = v
		return

	def show(self):
		for i in range(self.h + 2):
			print(self.cost[(self.w + 2) * i:(self.w + 2) * (i + 1)])

	def showsome(self, tgt):
		for t in tgt:
			print(t)
		return

	def showsomejoin(self, tgt):
		for t in tgt:
			print(''.join(t))
		return

	def search(self):
		grid = self.grid
		move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

class BIT:

	def __init__(self, n):
		self.n = n
		self.BIT = [0] * (n + 2)

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.n:
			self.BIT[idx] += x
			idx += idx & -idx
		return

	def show(self):
		print(self.BIT)

def solve():
	(n, m) = getList()
	graph = [getS() for i in range(n)]
	if m % 2 == 1:
		ans = []
		for i in range(m + 1):
			if i % 2 == 0:
				ans.append(1)
			else:
				ans.append(2)
		print('YES')
		print(*ans)
		return
	if n == 2:
		if graph[0][1] != graph[1][0]:
			print('NO')
			return
		else:
			ans = []
			for i in range(m + 1):
				if i % 2 == 0:
					ans.append(1)
				else:
					ans.append(2)
			print('YES')
			print(*ans)
			return
	anses = []
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if graph[i][j] == graph[j][i]:
				anses = [i, j]
				break
	if anses:
		ans = []
		for i in range(m + 1):
			ans.append(anses[i % 2] + 1)
		print('YES')
		print(*ans)
		return
	if graph[0][1] == graph[1][2]:
		if graph[1][2] == graph[2][0]:
			ans = []
			for i in range(m + 1):
				ans.append(i % 3 + 1)
			print('YES')
			print(*ans)
			return
		else:
			p4 = [2, 3, 2, 1]
			p6 = [1, 2, 3, 2]
	elif graph[0][2] == graph[0][1]:
		p4 = [3, 2, 3, 1]
		p6 = [1, 3, 2, 3]
	else:
		p4 = [1, 2, 1, 3]
		p6 = [3, 1, 2, 1]
	if m % 4 == 0:
		ans = []
		for i in range(m + 1):
			ans.append(p4[i % 4])
		print('YES')
		print(*ans)
		return
	else:
		ans = []
		for i in range(m + 1):
			ans.append(p6[i % 4])
		print('YES')
		print(*ans)
		return

def main():
	n = getN()
	for _ in range(n):
		solve()
	return
main()


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	A = [input() for i in range(n)]
	if m % 2 != 0:
		print('YES')
		for i in range(m + 1):
			if i % 2 == 0:
				print(1, end=' ')
			else:
				print(2, end=' ')
		print()
	else:
		(x, y) = (-1, -1)
		for i in range(n):
			for j in range(i + 1, n):
				if i != j and A[i][j] == A[j][i]:
					(x, y) = (i + 1, j + 1)
					break
		if x != -1:
			print('YES')
			for i in range(m + 1):
				if i % 2 == 0:
					print(x, end=' ')
				else:
					print(y, end=' ')
			print()
		else:
			(x, y, z) = (-1, -1, -1)
			for i in range(n):
				G = {}
				for j in range(n):
					if i != j:
						G[A[i][j]] = j + 1
				cnt = 0
				for j in G:
					cnt = cnt + 1
				if cnt == 2:
					x = G['a']
					z = G['b']
					y = i + 1
					break
			if x == -1:
				print('NO')
			else:
				print('YES')
				if m % 4 == 0:
					A1 = [z, y, x, y]
					ans = [y]
					v = m // 4
					for i in range(v):
						ans.extend(A1)
					print(*ans)
				else:
					ans = [x, y, z]
					if m == 2:
						print(*ans)
					else:
						A1 = [y, x, y, z]
						v = (m - 2) // 4
						for i in range(v):
							ans.extend(A1)
						print(*ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	(n, m) = RL()
	res = []
	for i in range(n):
		s = input()
		res.append(s)
	if n == 2:
		ans = AI(m + 1, 1)
		if m & 1:
			print('YES')
			for i in range(1, m + 1, 2):
				ans[i] = 2
			print(*ans)
		elif res[0][1] == res[1][0]:
			print('YES')
			for i in range(1, m + 1, 2):
				ans[i] = 2
			print(*ans)
		else:
			print('NO')
	else:
		sa = sb = -1
		print('YES')
		for i in range(1, 3):
			for j in range(i):
				if res[i][j] == res[j][i]:
					sa = i + 1
					sb = j + 1
					break
		if sa != -1:
			ans = AI(m + 1, sa)
			for i in range(1, m + 1, 2):
				ans[i] = sb
		elif m & 1:
			ans = AI(m + 1, 1)
			for i in range(1, m + 1, 2):
				ans[i] = 2
		elif res[0][1] == res[1][2] == res[2][0]:
			tmp = [1, 2, 3]
			ans = AI(m + 1, 1)
			for i in range(m + 1):
				ans[i] = tmp[i % 3]
		else:
			ans = A(m + 1)
			for i in range(3):
				ca = cb = 0
				for j in range(3):
					if j != i:
						if res[i][j] == 'a':
							ca += 1
						else:
							cb += 1
				if ca == 2:
					v1 = i + 1
				elif cb == 2:
					v2 = i + 1
				else:
					v3 = i + 1
			if m // 2 & 1:
				ans[0] = v1
				for i in range(1, m // 2 + 1):
					if i & 1:
						ans[i] = v3
					else:
						ans[i] = v1
				for i in range(m // 2 + 1, m + 1):
					if i & 1:
						ans[i] = v3
					else:
						ans[i] = v2
			else:
				ans[0] = v3
				for i in range(1, m // 2 + 1):
					if i & 1:
						ans[i] = v2
					else:
						ans[i] = v3
				for i in range(m // 2 + 1, m + 1):
					if i & 1:
						ans[i] = v1
					else:
						ans[i] = v3
		print(*ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7

def solve():
	if m & 1:
		print('YES')
		ans = [(i & 1) + 1 for i in range(m + 1)]
		print(*ans)
		return
	for i in range(n):
		for j in range(i):
			if ss[i][j] == ss[j][i]:
				print('YES')
				ans = [i + 1, j + 1] * (m // 2) + [i + 1]
				print(*ans)
				return
	if n == 2:
		print('NO')
		return
	for i in range(n):
		j = ss[i].find('a')
		k = ss[i].find('b')
		if j == -1 or k == -1:
			continue
		if m % 4:
			ans = [i + 1 if c % 2 else j + 1 for c in range(m // 2 + 1)]
		else:
			ans = [j + 1 if c % 2 else i + 1 for c in range(m // 2 + 1)]
		ans += [i + 1 if c % 2 else k + 1 for c in range(m // 2)]
		print('YES')
		print(*ans)
		return
for _ in range(II()):
	(n, m) = MI()
	ss = [SI() for _ in range(n)]
	solve()


from sys import stdin, exit
from bisect import bisect_left as bl, bisect_right as br
from itertools import accumulate
input = lambda : stdin.readline()[:-1]
intput = lambda : int(input())
sinput = lambda : input().split()
intsput = lambda : map(int, sinput())

def dprint(*args, **kwargs):
	if debugging:
		print(*args, **kwargs)

def label(i, j):
	return matrix[i][j]
debugging = 1
t = intput()
for _ in range(t):
	matrix = []
	(n, m) = intsput()
	for i in range(n):
		matrix.append(input())
	if m % 2:
		print('YES')
		ans = []
		for i in range(m + 1):
			ans.append(i % 2 + 1)
		print(' '.join(map(str, ans)))
	else:
		done = False
		for i in range(n):
			for j in range(i + 1, n):
				first = label(i, j)
				second = label(j, i)
				if first == second:
					print('YES')
					print(' '.join([str(i + 1), str(j + 1)] * (m // 2) + [str(i + 1)]))
					done = True
					break
			if done:
				break
		if done:
			continue
		for i in range(n):
			options = set(matrix[i])
			if len(options) == 3:
				a = i
				for b in range(n):
					if matrix[i][b] == 'a':
						break
				for c in range(n):
					if matrix[i][c] == 'b':
						break
				print('YES')
				ans = []
				if m % 4 == 0:
					ans.append(a)
					for k in range(m // 4):
						ans.append(b)
						ans.append(a)
					for k in range(m // 4):
						ans.append(c)
						ans.append(a)
				else:
					ans.append(b)
					for k in range(m // 2):
						if k % 2 == 0:
							ans.append(a)
							ans.append(c)
						else:
							ans.append(a)
							ans.append(b)
				print(' '.join(map(str, map(lambda x: x + 1, ans))))
				done = True
				break
		else:
			print('NO')


from sys import stdin, stdout
from random import randint

def solve(tc):
	(n, m) = map(int, stdin.readline().split())
	grid = []
	for i in range(n):
		grid.append(stdin.readline().strip())
	ans = []
	for i in range(n):
		for j in range(i + 1, n):
			if grid[i][j] == grid[j][i]:
				for k in range(m + 1):
					if len(ans) & 1:
						ans.append(i + 1)
					else:
						ans.append(j + 1)
				print('YES')
				print(' '.join(map(lambda x: str(x), ans)))
				return
	if m % 2:
		for k in range(m + 1):
			if len(ans) & 1:
				ans.append(1)
			else:
				ans.append(2)
		print('YES')
		print(' '.join(map(lambda x: str(x), ans)))
		return
	if n == 2:
		print('NO')
		return
	pick = []
	while True:
		while len(pick) < 3:
			num = randint(0, n - 1)
			if num not in pick:
				pick.append(num)
		if grid[pick[0]][pick[1]] == grid[pick[1]][pick[2]]:
			break
		else:
			pick.clear()
	if m == 2:
		ans.append(pick[0] + 1)
		ans.append(pick[1] + 1)
		ans.append(pick[2] + 1)
	else:
		if m // 2 & 1:
			ans.append(pick[0] + 1)
			ans.append(pick[2] + 1)
		else:
			ans.append(pick[2] + 1)
			ans.append(pick[0] + 1)
		while len(ans) < m // 2:
			ans.append(ans[-2])
		ans.append(pick[1] + 1)
		ans.append(pick[2] + 1)
		p = 0
		while len(ans) <= m:
			if p & 1:
				ans.append(pick[2] + 1)
			else:
				ans.append(pick[0] + 1)
			p += 1
	print('YES')
	print(' '.join(map(lambda x: str(x), ans)))
tcs = 1
tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	S = [input()[:-1] for _ in range(n)]
	(x, y) = (-1, -1)
	for i in range(n):
		for j in range(i + 1, n):
			if S[i][j] == S[j][i]:
				(x, y) = (i, j)
	if m % 2 == 1 and x == -1:
		(x, y) = (0, 1)
	if x != -1:
		ans = [x + 1]
		for i in range(m):
			if i % 2 == 0:
				ans.append(y + 1)
			else:
				ans.append(x + 1)
		print('YES')
		print(*ans)
		continue
	(x, y, z) = (-1, -1, -1)
	for i in range(n):
		(ax, bx, az, bz) = (-1, -1, -1, -1)
		for j in range(n):
			if S[j][i] == 'a':
				ax = j
			elif S[j][i] == 'b':
				bx = j
			if S[i][j] == 'a':
				az = j
			elif S[i][j] == 'b':
				bz = j
		if ax != -1 and az != -1:
			(x, y, z) = (ax, i, az)
			break
		elif bx != -1 and bz != -1:
			(x, y, z) = (bx, i, bz)
			break
	if x != -1:
		print('YES')
		if m % 4 == 0:
			print(*[y + 1] + [x + 1, y + 1, z + 1, y + 1] * (m // 4))
		else:
			print(*[z + 1, y + 1, x + 1] + [y + 1, z + 1, y + 1, x + 1] * ((m - 2) // 4))
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	e = [list(input())[:-1] for _ in range(N)]
	res = [0] * (M + 1)
	for i in range(N):
		for j in range(N):
			if i == j:
				continue
			if e[i][j] == e[j][i]:
				for k in range(M + 1):
					if k % 2:
						res[k] = i + 1
					else:
						res[k] = j + 1
				break
		else:
			continue
		break
	if res[0]:
		print('YES')
		print(*res)
		continue
	if M % 2:
		for k in range(M + 1):
			if k % 2:
				res[k] = 1
			else:
				res[k] = 2
		print('YES')
		print(*res)
		continue
	else:
		for i in range(N):
			a = -1
			b = -1
			for j in range(N):
				if e[i][j] == 'a':
					a = j
				if e[i][j] == 'b':
					b = j
			if a >= 0 and b >= 0:
				if M % 4 == 0:
					for k in range(M + 1):
						if k % 4 == 0:
							res[k] = i + 1
						elif k % 4 == 1:
							res[k] = a + 1
						elif k % 4 == 2:
							res[k] = i + 1
						elif k % 4 == 3:
							res[k] = b + 1
				else:
					for k in range(M // 2 + 1):
						if k % 2 == 0:
							res[k] = a + 1
						elif k % 2 == 1:
							res[k] = i + 1
					for k in range(M // 2 + 1, M + 1):
						if k % 2 == 0:
							res[k] = b + 1
						elif k % 2 == 1:
							res[k] = i + 1
				print('YES')
				print(*res)
				break
		else:
			print('NO')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	(n, m) = RL()
	g = [S() for _ in range(n)]
	if m & 1:
		print('YES')
		print_list([1, 2] * (m + 1 >> 1))
	else:
		(x, y) = (None, None)
		for i in range(n - 1):
			for j in range(i + 1, n):
				if g[i][j] == g[j][i]:
					(x, y) = (i + 1, j + 1)
					break
			if x:
				break
		if x:
			print('YES')
			print_list([x, y] * (m >> 1) + [x])
		else:
			f = False
			for x in range(n):
				for y in range(n):
					if x == y:
						continue
					c = g[x][y]
					for z in range(n):
						if g[y][z] == c:
							print('YES')
							f = True
							x += 1
							y += 1
							z += 1
							if m % 4 == 0:
								print_list([y] + [x, y, z, y] * (m // 4))
							else:
								print_list([x, y, z] + [y, x, y, z] * (m // 4))
							break
					if f:
						break
				if f:
					break
			if not f:
				print('NO')


import sys
input = sys.stdin.readline
import math
import copy
import collections
from collections import deque
import heapq
import itertools
from collections import defaultdict
from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	adj = []
	if n < 3:
		for i in range(n):
			adj.append([])
			temp = input().rstrip()
			for c in temp:
				adj[i].append(c)
		poss = False
		if m & 1:
			poss = True
		if adj[0][1] == adj[1][0]:
			poss = True
		ans = [1, 2] * m
		if poss:
			print('YES')
			for i in range(m + 1):
				print(ans[i], end=' ')
			print()
		else:
			print('NO')
	else:
		for i in range(3):
			adj.append([])
			temp = input().rstrip()
			for j in range(3):
				adj[i].append(temp[j])
		for i in range(3, n):
			input()
		cycle = False
		(a, b) = [0, 1]
		for i in range(3):
			for j in range(i, 3):
				if adj[i][j] == adj[j][i] and i != j:
					a = i
					b = j
					cycle = True
		if cycle or m & 1:
			ans = [a, b] * m
			print('YES')
			for i in range(m + 1):
				print(ans[i] + 1, end=' ')
			print()
		else:
			(a, b, c) = [-1, -1, -1]
			for x in range(3):
				for y in range(3):
					for z in range(3):
						if x != y and x != z and (y != z) and (adj[x][y] == adj[y][z]):
							a = x
							b = y
							c = z
			if m % 4 == 0:
				ans = [b, a] * (m // 4) + [b, c] * (m // 4) + [b]
				print('YES')
				for i in range(m + 1):
					print(ans[i] + 1, end=' ')
				print()
			else:
				ans = [a, b] * (m // 4) + [a, b, c] + [b, c] * (m // 4)
				print('YES')
				for i in range(m + 1):
					print(ans[i] + 1, end=' ')
				print()


import sys

def soll(Var, m):
	if m % 2 == 1:
		answer = []
		for k in range(m + 1):
			if k % 2 == 0:
				answer.append(Var[0] + 1)
			else:
				answer.append(Var[1] + 1)
		print('YES')
		print(*answer)
		return
	A = []
	B = []
	for i in range(m // 2 + 1):
		if i % 2 == 0:
			curA = 1
			curB = 1
		elif i % 4 == 1:
			curA = 0
			curB = 2
		else:
			curA = 2
			curB = 0
		A.append(Var[curA])
		B.append(Var[curB])
	answer = list(reversed(B)) + A[1:]
	print('YES')
	for elem in answer:
		print(elem + 1, sep=' ')
	return

def sol():
	(n, m) = map(int, sys.stdin.readline().split())
	if m % 2 == 1:
		for i in range(n):
			input()
		answer = [i % 2 + 1 for i in range(m + 1)]
		print('YES')
		print(*answer)
		return
	if n == 2:
		x = sys.stdin.readline()[1]
		y = sys.stdin.readline()[0]
		if x != y:
			print('NO')
			return
		else:
			answer = [i % 2 + 1 for i in range(m + 1)]
			print('YES')
			print(*answer)
			return
	G = [[], [], []]
	for i in range(3):
		G[i] = sys.stdin.readline()[:3]
	for i in range(n - 3):
		sys.stdin.readline()
	for i in range(3):
		for j in range(i):
			if G[i][j] == G[j][i]:
				answer = []
				for k in range(m + 1):
					if k % 2 == 0:
						answer.append(i + 1)
					else:
						answer.append(j + 1)
				print('YES')
				print(*answer)
				return
	if G[0][1] == G[1][2]:
		soll([0, 1, 2], m)
		return
	if G[2][0] == G[0][1]:
		soll([2, 0, 1], m)
		return
	soll([1, 2, 0], m)
	return
for iter in range(int(sys.stdin.readline())):
	sol()


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	(n, m) = value()
	a = []
	for i in range(n):
		a.append(input())
	aa = False
	ab = False
	for i in range(n):
		aEle = False
		bEle = False
		aaEle = False
		for j in range(n):
			if i == j:
				continue
			if a[i][j] == 'a':
				aEle = j + 1
			if a[i][j] == 'b':
				bEle = j + 1
			if a[i][j] == a[j][i]:
				aaEle = j + 1
		if aaEle:
			aa = (i + 1, aaEle)
		if aEle and bEle:
			ab = (aEle, i + 1, bEle)
	if m % 2:
		print('YES')
		ans = [1, 2] * m
		print(*ans[:m + 1])
	elif aa:
		print('YES')
		ans = list(aa) * m
		print(*ans[:m + 1])
	elif ab:
		print('YES')
		(x, y, z) = ab
		if m // 2 % 2:
			here1 = [z, y] * (m // 2)
			here2 = [x, y] * (m // 2)
			ans = here1[:m // 2 + 1] + here2[:m // 2]
			print(*ans)
		else:
			here1 = [y, z] * (m // 2)
			here2 = [x, y] * (m // 2)
			ans = here1[:m // 2 + 1] + here2[:m // 2]
			print(*ans)
	else:
		print('NO')


import collections, sys, functools, heapq, bisect, math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	mat = []
	for i in range(n):
		mat.append(input().strip())
	if m % 2:
		print('YES')
		print(('1 2 ' * (m // 2 + 1)).strip(' '))
		continue
	for i in range(n):
		for j in range(i + 1, n):
			if mat[i][j] == mat[j][i]:
				print('YES')
				s = str(i + 1) + ' ' + str(j + 1) + ' '
				print(s * (m // 2) + str(i + 1))
				break
		else:
			continue
		break
	else:
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if i == j or j == k or k == i:
						continue
					if mat[i][j] == mat[j][k]:
						if m // 2 % 2:
							res = [str(i + 1), str(j + 1), str(k + 1), str(j + 1)]
						else:
							res = [str(j + 1), str(k + 1), str(j + 1), str(i + 1)]
						ans = []
						for ele in range(m + 1):
							ans.append(res[ele % 4])
						print('YES')
						print(' '.join(ans))
						break
				else:
					continue
				break
			else:
				continue
			break
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	grid = [input() for _ in range(n)]
	if m % 2 == 1:
		print('YES')
		print('1 2 ' * ((m + 1) // 2))
		continue
	for i in range(n):
		found = False
		for j in range(n):
			if j == i:
				continue
			for k in range(n):
				if k == i:
					continue
				if grid[j][i] == grid[i][k]:
					found = True
					break
			if found:
				break
		if found:
			break
	else:
		print('NO')
		continue
	i += 1
	j += 1
	k += 1
	if j == k:
		print('YES')
		print(i, f'{j} {i} ' * (m // 2))
	else:
		print('YES')
		if m // 2 % 2 == 0:
			print(f'{k} {j} ' * (m // 4) + f'{i} ' + f'{k} {j} ' * (m // 4))
		else:
			print(j, f'{k} {j} ' * ((m - 2) // 4) + f'{i} ' + f'{k} {j} ' * ((m - 2) // 4) + f'{k}')


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = [input() for i in range(n)]
	same = False
	(u, t) = (-1, -1)
	for i in range(n):
		for j in range(i + 1, n):
			if s[i][j] == s[j][i]:
				(u, t) = (i, j)
				same = True
	if same:
		print('YES')
		ans = [0 for i in range(m + 1)]
		for i in range(m + 1):
			if i % 2 == 0:
				ans[i] = u + 1
			else:
				ans[i] = t + 1
		print(*ans)
		continue
	elif m % 2 == 1:
		print('YES')
		ans = [0 for i in range(m + 1)]
		for i in range(m + 1):
			if i % 2 == 0:
				ans[i] = 1
			else:
				ans[i] = 2
		print(*ans)
		continue
	A = [-1 for i in range(n)]
	B = [-1 for i in range(n)]
	for i in range(n):
		for j in range(n):
			if s[i][j] == 'a':
				A[i] = j
			elif s[i][j] == 'b':
				B[i] = j
	(u, t, mid) = (-1, -1, -1)
	for i in range(n):
		for j in range(n):
			if s[i][j] == 'a' and A[j] != -1:
				(u, t, mid) = (i, A[j], j)
			elif s[i][j] == 'b' and B[j] != -1:
				(u, t, mid) = (i, B[j], j)
	if u != -1:
		print('YES')
		k = m // 2
		if (k - 1) % 2 == 1:
			L = k // 2
			ans = [mid + 1, u + 1] * L + [mid + 1] + [t + 1, mid + 1] * L
		else:
			L = k // 2
			ans = [u + 1, mid + 1] * L + [u + 1, mid + 1, t + 1] + [mid + 1, t + 1] * L
		print(*ans)
		assert len(ans) == m + 1
		continue
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = [input() for _ in range(n)]
	flg = 0
	for i in range(n):
		for j in range(i + 1, n):
			if s[i][j] == s[j][i]:
				print('YES')
				res = [i + 1] * (m + 1)
				for k in range(1, m + 1, 2):
					res[k] = j + 1
				print(*res)
				flg = 1
				break
		if flg:
			break
	else:
		if m % 2 == 1:
			print('YES')
			res = [1] * (m + 1)
			for k in range(1, m + 1, 2):
				res[k] = 2
			print(*res)
		else:
			p = [-1] * n
			q = [-1] * n
			for i in range(n):
				for j in range(n):
					if s[i][j] == 'a':
						p[i] = j + 1
						q[j] = i + 1
			for i in range(n):
				if p[i] > 0 and q[i] > 0:
					print('YES')
					res = [i + 1] * (m + 1)
					if m % 4 == 2:
						for k in range(0, m + 1, 4):
							res[k] = q[i]
						for k in range(2, m + 1, 4):
							res[k] = p[i]
					else:
						for k in range(3, m + 1, 4):
							res[k] = q[i]
						for k in range(1, m + 1, 4):
							res[k] = p[i]
					print(*res)
					break
			else:
				print('NO')


import sys
read = sys.stdin.readline
write = lambda x, end='\n': sys.stdout.write(x + end)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = [input()[:3] for _ in range(n)][:3]
	if m & 1:
		print('YES')
		print(' '.join(('1' if i & 1 else '2' for i in range(m + 1))))
	elif g == ['*a', 'b*'] or g == ['*b', 'a*']:
		print('NO')
	elif len(g) == 2:
		print('YES')
		print(' '.join(('1' if i & 1 else '2' for i in range(m + 1))))
	else:
		db = False
		for y in range(3):
			for x in range(3):
				if y != x and g[y][x] == g[x][y]:
					print('YES')
					print(' '.join((str(y + 1) if i & 1 else str(x + 1) for i in range(m + 1))))
					db = True
					break
			if db:
				break
		else:
			if g[0][1] == g[1][2] == g[2][0]:
				print('YES')
				print(' '.join((str(i % 3 + 1) for i in range(m + 1))))
			else:
				x = 1 if g[0][1] != g[0][2] else 2 if g[1][0] != g[1][2] else 3
				(y, z) = {1, 2, 3} - {x}
				if m & 2:
					print('YES')
					print(' '.join((str(x if i & 1 == 0 else y if i & 2 == 0 else z) for i in range(1, m + 2))))
				else:
					print('YES')
					print(' '.join((str(x if i & 1 == 0 else y if i & 2 == 0 else z) for i in range(m + 1))))


rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
YN = lambda x: print('YES') if x else print('NO')
pl = lambda l: print(' '.join(list(map(str, l))))

def d(a):
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	return d
for _ in range(rn()):
	(n, m) = rns()
	grid = []
	for i in range(n):
		grid.append(rs())
	if m % 2 == 1:
		print('YES')
		print((m + 1) // 2 * '1 2 ')
	else:
		flag = False
		pair = ''
		for i in range(n):
			for j in range(n):
				if i != j and grid[i][j] == grid[j][i]:
					flag = True
					pair = str(i + 1) + ' ' + str(j + 1) + ' '
					break
		if flag:
			print('YES')
			print(m // 2 * pair + pair.split()[0])
		elif n == 2:
			print('NO')
		else:
			triplet = []
			for i in range(n):
				if len(set(grid[i])) == 3:
					triplet = [i + 1, grid[i].index('a') + 1, grid[i].index('b') + 1]
					break
			a = str(triplet[0]) + ' ' + str(triplet[1]) + ' '
			b = str(triplet[2]) + ' ' + str(triplet[0]) + ' '
			print('YES')
			if m // 2 % 2 == 0:
				print(m // 4 * a + str(triplet[0]) + ' ' + m // 4 * b)
			else:
				m -= 2
				print(str(triplet[1]) + ' ' + m // 4 * a + str(triplet[0]) + ' ' + m // 4 * b + str(triplet[2]))


from itertools import cycle, islice
from sys import stdin
readline = stdin.readline

def read_ints():
	return map(int, readline().split())

def read_string():
	return readline()[:-1]

def f(a_seq, b_seq, c_seq):
	assert len(a_seq) == len(b_seq)
	n = len(a_seq)
	colors_need = Counter((b for (a, b) in zip(a_seq, b_seq) if a != b))
	colors_has = Counter(c_seq)
	if any((colors_has[c] < required_n for (c, required_n) in colors_need.items())):
		raise ValueError
	indices_by_required_colors = defaultdict(list)
	for i in range(n):
		if b_seq[i] != a_seq[i]:
			indices_by_required_colors[b_seq[i]].append(i)
	if c_seq[-1] not in b_seq:
		raise ValueError
	if c_seq[-1] in indices_by_required_colors:
		i_swap = indices_by_required_colors[c_seq[-1]][0]
	else:
		i_swap = b_seq.index(c_seq[-1])
	for c in c_seq:
		if c in indices_by_required_colors:
			yield indices_by_required_colors[c].pop()
			if not indices_by_required_colors[c]:
				del indices_by_required_colors[c]
		else:
			yield i_swap

def f(graph, m):
	assert n >= 2
	assert m >= 1
	for u in range(n):
		for v in range(u + 1, n):
			if graph[u][v] == graph[v][u]:
				return list(islice(cycle([u, v]), m + 1))
	if m % 2 != 0:
		return list(islice(cycle([0, 1]), m + 1))
	if n == 2:
		raise ValueError
	g = [('a' in row, 'b' in row) for row in graph]
	for u in range(n):
		for v in range(n):
			if u != v:
				ch = graph[u][v]
				if g[v][ord(ch) - ord('a')]:
					w = graph[v].index(ch)
					base = [u, v, w]
					v_need = m + 1 - 3
					if v_need == 0:
						return base
					v_at_half = v_need // 2
					return list(islice(cycle([v, u]), v_at_half))[::-1] + base + list(islice(cycle([v, w]), v_at_half))
	raise ValueError
(t_n,) = read_ints()
for i_t in range(t_n):
	(n, m) = read_ints()
	graph = [read_string() for i_row in range(n)]
	try:
		path = f(graph, m)
	except ValueError:
		print('NO')
	else:
		print('YES')
		print(*[v + 1 for v in path])