Известный герой компьютерной игры ёжик Соник находится в запутанном подземелье. Лабиринт состоит из комнат, соединённых коридорами. В каждой комнате храниться по одному золотому кольцу, которые должен собрать ёжик для защиты от смерти. Необходимо обойти все комнаты лабиринта и собрать кольца. Соник знает один надежный способ обойти все подземелье, ему об этом рассказывал его верный друг Майлз. Майлз называл этот метод BFS. Соник точно не знает, что это значит, но всегда использовал его в сложных ситуациях.
Входные данные:
В первой сроке указано N – количество комнат в подземелье и S - номер стартовой комнаты. Лабиринт комнат задан таблицей размером N на N, где N — количество комнат. Если две комнаты связаны коридором, соответствующий элемент равен 1, иначе — 0. Нумерация комнат начинается с 1.
Выходные данные:
Если Соник может обойти все комнаты лабиринт за один проход, то надо вывести в одну строку номера комнат в порядке обхода.
Если единого пути через все комнаты нет, то вывести слово НЕТ
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
0 1 0
1 0 1
0 1 0
|
1 2 3
|
|
2
|
3 1
0 1 0
1 0 0
0 0 0
|
НЕТ
|