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