CF1481D AB Graph

你的朋友 Salem 是 Warawreh 的兄弟，他只喜欢数学和几何题。他已经解决了很多这类问题，但据 Warawreh 所说，为了从大学毕业，他还需要解决更多的图论问题。由于 Salem 不擅长图论，他请求你帮忙解决下面这个问题。 你得到一个没有自环的完全有向图，共有 $n$ 个顶点。换句话说，你有 $n$ 个顶点，对于每一对不同的顶点 $u$ 和 $v$（$u \neq v$），都有有向边 $(u, v)$ 和 $(v, u)$。 图中每条有向边都被标记为一个字符：'a' 或 'b'（边 $(u, v)$ 和 $(v, u)$ 的标记可以不同）。 你还得到一个整数 $m > 0$。你需要找到一条长度为 $m$ 的路径，使得沿着路径经过的边的标记依次写出后得到的字符串是回文串。路径的长度指的是边的数量。 你可以多次访问同一个顶点和同一条有向边。

第一行包含一个整数 $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$ 的边上的字符。 如果 $i \neq j$，该字符为 'a' 或 'b'；如果 $i = j$，该字符为 '*'，因为图中没有自环。 保证所有测试用例中 $n$ 的总和不超过 $1000$，$m$ 的总和不超过 $10^5$。

对于每个测试用例，如果存在这样的路径，输出 "YES" 并输出路径本身，即 $m+1$ 个整数，表示路径上依次经过的顶点编号。如果有多种合法路径，输出任意一种即可。 否则（如果不存在这样的路径），输出 "NO"。

下图展示了前三个测试用例的图： 在第一个测试用例中，答案序列为 $[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。 由 ChatGPT 4.1 翻译