Ваш друг Salem — брат Warawreh, и ему нравятся только математические и геометрические задачи. Он решил уже множество таких задач, но, по словам Warawreh, чтобы успешно окончить университет, ему нужно решать больше графовых задач. Так как Salem не очень хорош в графах, он попросил вас помочь ему с такой задачей.
Вам задан полный ориентированный граф из \(n\) вершин без петель. Другими словами, у вас есть \(n\) вершин, и для каждой пары вершин \(u\) и \(v\) (\(u \neq v\)) есть две направленных дуги \((u, v)\) и \((v, u)\).
На каждой направленной дуге графа написано по одной букве: либо «a», либо «b» (дуги \((u, v)\) и \((v, u)\) могут иметь различные метки).
Вам также задано целое число \(m > 0\). Вам нужно найти путь длины \(m\) такой, что строка, полученная выписыванием букв на дугах в порядке из обхода, будет являться палиндромом. Длина пути — это количество дуг в нем.
Вы можете посещать одни и те же вершины и дуги произвольное количество раз.
Выходные данные
Для каждого набора входных данных, если возможно найти такой путь, выведите «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.
Примеры
| № | Входные данные | Выходные данные |
|
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*
|
YES
1 2
YES
2 1 3 2
YES
1 3 1 3 1
YES
1 2 1 3 4 1 4
NO
|