Задача 12. Экскурсия по Италии 2 ≡

Условие

Проехав по городу, Молния Маквин, Луиджи и Гвидо решают посетить различные туристические места, которые были указаны у них в путеводителе. Но времени у них осталось уже не так много, а успеть посетить все очень хочется.

Чтобы успеть везде побывать они хотят найти самый оптимальный маршрут. Достопримечательности могут быть связаны между собой дорогой, а могут быть совершенно в другом месте. Каждую достопримечательность нужно посетить лишь единожды. Начальная точка экскурсии и количество достопримечательностей выбираются с самого начала.

Ваша задача понять, возможно ли проехать по всем достопримечательностям, посетив каждую лишь единожды.

Формат входных данных

На вход подается число N и S.

N - количество достопримечательностей.

S - начальная точка

После чисел следует матрица смежности графа размерностью N.

Формат выходных данных

Вывести последовательность номеров вершин, которые персонажам предстоит посетить, иначе вывести "Нет решения"

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

Примеры тестов

9 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 1 0 1
1 0 0 0 1 1 0 0 1
1 1 0 0 0 1 0 0 1
0 0 1 0 0 1 0 1 0
0 0 1 1 1 0 1 0 1
1 1 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 0 1 0
            

1 3 0 2 4 7 8 5 6 1

6 0
0 1 0 0 0 0
1 0 0 1 0 1
0 0 0 0 0 1
0 1 0 0 0 1
0 0 0 0 0 0
0 1 1 1 0 0
            

Нет решения