考虑二元环 要是二元环相同 那么显然怎么构造都可以了
否则 我们考虑 没有二元环相同
要是m是奇数 我们随便跑跑就行
要是m是偶数 情况呢
我们需要构造一种情况
我们肯定用的点数越少越好
我们考虑三个点
要是两个二元环都是 a 出 或者 b 出的
就可以构造出来了
void solve(){
int n,m;cin>>n>>m;
char A[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>A[i][j];
}
}
vector<PII>t,bt;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(A[i][j]==A[j][i])t.push_back({i,j});
else bt.push_back({i,j});
}
}
if(m&1){
if(bt.size()){
YES
auto [u,v]=bt.back();
for(int i=0;i<m+1;i++){
if(i&1)cout<<u<<' ';
else cout<<v<<' ';
}
}else{
YES
auto [u,v]=t.back();
for(int i=0;i<m+1;i++){
if(i&1)cout<<u<<' ';
else cout<<v<<' ';
}
}
}else{
if(t.size()){
YES
auto [u,v]=t.back();
for(int i=0;i<m+1;i++){
if(i&1)cout<<u<<' ';
else cout<<v<<' ';
}
}else{
vector<int>a[n+1],b[n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(A[i][j]=='a')a[i].push_back(j);
else b[i].push_back(j);
}
}
if(m/2%2){
for(int u=1;u<=n;u++){
for(auto v1:a[u]){
if(a[v1].size()){
auto v2=a[v1].back();
YES
cout<<u<<' ';
for(int i=1;i<=m/2;i++){
if(i&1)cout<<v1<<' ';
else cout<<u<<' ';
}
for(int i=1;i<=m/2;i++){
if(i&1)cout<<v2<<' ';
else cout<<v1<<' ';
}
cout<<endl;
return;
}
}
}
}else{
for(int u=1;u<=n;u++){
if(a[u].size()&&b[u].size()){
auto v1=a[u].back();
auto v2=b[u].back();
YES
cout<<u<<' ';
for(int i=1;i<=m/2;i++){
if(i&1)cout<<v1<<' ';
else cout<<u<<' ';
}
for(int i=1;i<=m/2;i++){
if(i&1)cout<<v2<<' ';
else cout<<u<<' ';
}
cout<<endl;
return;
}
}
}
NO
}
}
cout<<endl;
}