你的朋友塞勒姆是瓦拉雷的兄弟,只喜欢数学和几何问题。他已经解决了很多这样的问题,但根据 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。