CF1481D.AB Graph

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 \gt 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.

你的朋友萨勒姆是瓦拉维赫的兄弟，他只喜欢数学和几何问题。他已解决过大量此类问题，但据瓦拉维赫所说，为了从大学毕业，他必须再多解一些图论问题。由于萨勒姆不擅长图论，他向你求助以下问题。

给你一个含 $n$ 个顶点的完全有向图，且图中不含自环。换言之，你拥有 $n$ 个顶点，且对任意两个不同顶点 $u$ 和 $v$（即 $u \neq v$），均存在两条有向边 $(u, v)$ 和 $(v, u)$。

图中每条有向边均被标记为单个字符：要么是 'a'，要么是 'b'（注意：边 $(u, v)$ 与 $(v, u)$ 的标签可以不同）。

你还给定一个正整数 $m > 0$。你需要找出一条长度为 $m$ 的路径，使得沿该路径遍历时所经过的各边标签按顺序拼接而成的字符串是一个回文串。此处路径的长度定义为路径中所含边的数量。

你可以重复访问同一顶点，也可以重复经过同一条有向边任意多次。

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$.

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 1000$；$1 \leq m \leq 10^{5}$）—— 图中顶点的数量以及所期望的回文串长度。

接下来的 $n$ 行，每行包含 $n$ 个字符。第 $i$ 行的第 $j$ 个字符表示从节点 $i$ 指向节点 $j$ 的边上的字符。

每个字符要么是 'a' 或 'b'（当 $i \neq j$ 时），要么是 '*'（当 $i = j$ 时），因为图中不含自环。

保证所有测试用例的 $n$ 之和不超过 $1000$，且所有测试用例的 $m$ 之和不超过 $10^5$。

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".

对于每个测试用例，若存在满足条件的路径，则输出 "YES"，并紧接着输出该路径本身：一个由 $m + 1$ 个整数组成的序列，表示路径中各顶点的下标（按正确顺序排列）。若存在多个合法路径，输出任意一个即可。

否则（即不存在满足条件的路径），输出 "NO"。

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.

前三个测试用例对应的图如下所示：

在第一个测试用例中，答案序列为 $[1,2]$，表示路径为：

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

因此，该路径所生成的字符串为 b。

在第二个测试用例中，答案序列为 $[2,1,3,2]$，表示路径为：

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

因此，该路径所生成的字符串为 bab。

在第三个测试用例中，答案序列为 $[1,3,1,3,1]$，表示路径为：

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

因此，该路径所生成的字符串为 aaaa。

第四个测试用例中生成的字符串为 abaaba。