← 返回题目列表

Codeforces · 1481/D

D. AB 图

中文机器翻译题面 查看原题

你的朋友塞勒姆是瓦拉雷的兄弟,只喜欢数学和几何问题。他已经解决了很多这样的问题,但根据 Warawreh 的说法,为了从大学毕业,他必须解决更多的图形问题。由于塞勒姆不擅长图表,他请求你帮助解决以下问题。

给你一个完整的有向图,其中有 $$$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

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*

输出 #1

YES
1 2
YES
2 1 3 2
YES
1 3 1 3 1
YES
1 2 1 3 4 1 4
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。