分类讨论。

【11】当 mm 是奇数时，构造 $ \text{abababab} \cdots$ 的串即可满足题意，于是直接交替输出 11 和 22 凑足 m+1m+1 个即可。

【22】当 mm 是偶数时：

【2.12.1】存在一个点对，来回字母一样，如下图：

这时显然和【11】相同处理即可。

【2.22.2】存在三个点，路径上字母相同，如下图：

这时构造一个 ⋯1→2→1→2→3→2→3⋯\cdots 1\rightarrow2\rightarrow\boxed{1\rightarrow2\rightarrow3}\rightarrow2\rightarrow3\cdots 的解即可，具体详见代码。

作为一道细节题，你应该自己实现代码和调试，不建议直接读代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
#define int long long
using namespace std;
string mp[1001];
int tota[1001];
int totb[1001];
int n,m;
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>mp[i];
		mp[i]=" "+mp[i];
		tota[i]=totb[i]=0;
		for(int j=1;j<=n;j++){
			if(mp[i][j]=='a'){
				tota[j]++;
			}
			else if(mp[i][j]!='b'){
				totb[j]++;
			}
		}
	}
	if(m%2!=0){
		cout<<"YES"<<endl;
		for(int i=1;i<=m+1;i++){
			if(i%2){
				cout<<"1 ";
			}
			else{
				cout<<"2 ";
			}
		}
		cout<<endl;
		return;
	}
	bool flag=false;
	int x=0,y=0,z=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&mp[i][j]==mp[j][i]){
				x=i,y=j;
				flag=true;
				break;
			}
		}
		if(flag)break;
	}
	if(x*y!=0){
		cout<<"YES"<<endl;
		for(int i=1;i<=m+1;i++){
			if(i%2){
				cout<<x<<" ";
			}
			else{
				cout<<y<<" ";
			}
		}
		cout<<endl;
		return;
	}
	flag=false;
	x=y=z=0;
	if(n<=2){
		cout<<"NO"<<endl;
		return;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&((mp[i][j]=='a'&&tota[j]>=1)||(mp[i][j]=='b'&&totb[j]>=1))){
				for(int k=1;k<=n;k++){
					if(mp[j][k]==mp[i][j]){
						x=i,y=j,z=k;
					}
				}
				if(x*y*z!=0){
					flag=true;
					break;
				}
			}
		}
		if(flag)break;
	}
	if(x*y*z==0){
		cout<<"NO"<<endl;
		return;
	}
//	cerr<<x<<" "<<y<<" "<<z<<endl;
	if((m-2)/2%2==0){
		cout<<"YES"<<endl;
		for(int i=1;i<=m/2-1;i++){
			if(i%2){
				cout<<x<<" ";
			}
			else{
				cout<<y<<" ";
			}
		}
		cout<<x<<" "<<y<<" "<<z<<" ";
		for(int i=m/2+3;i<=m+1;i++){
			if(i%2){
				cout<<z<<" ";
			}
			else{
				cout<<y<<" ";
			}
		}
		cout<<endl;
		return;
	}
	else{
		cout<<"YES"<<endl;
		for(int i=1;i<=m/2-1;i++){
			if(i%2){
				cout<<y<<" ";
			}
			else{
				cout<<x<<" ";
			}
		}
		cout<<x<<" "<<y<<" "<<z<<" ";
		for(int i=m/2+3;i<=m+1;i++){
			if(i%2){
				cout<<y<<" ";
			}
			else{
				cout<<z<<" ";
			}
		}
		cout<<endl;
		return;
	}
	cout<<"NO"<<endl;
}
signed main(){
#ifdef USE_FILE_IO
	freopen("code.in","r",stdin);
	cerr<<"[File IO]"<<endl;
#endif
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}