D. AB граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваш друг 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$$$ символов. $$$j$$$-й символ $$$i$$$-й строки описывает символ, написанный на дуге из вершины $$$i$$$ в вершину $$$j$$$.

Каждый символ — это «a» или «b», если $$$i \neq j$$$, либо же «*», если $$$i = j$$$, так как граф не содержит петель.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$ и сумма $$$m$$$ не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных, если возможно найти такой путь, выведите «YES» и сам путь как последовательность из $$$m + 1$$$ целых чисел: номера вершин в пути в порядке обхода. Если существует несколько возможных путей, выведите любой из них.

В противном случае (если ответа нет), выведите «NO».

Пример
Входные данные
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*
Выходные данные
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.