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