Группа школьников создала социальную сеть, где каждый участник дружит с несколькими другими школьниками. Сеть стала очень популярной среди школьников и через месяц ее участниками стали N школьников. Организаторы сети задумались, можно ли соединить всех ребят друг с другом, начиная с S-го участника, и составить единую «цепочку дружбы», чтобы она охватывала всех участников этой социальной сети (то есть определить, существует ли связь напрямую или через друзей между любой парой школьников, начиная с S-го участника). Одни из ребят предложил для решения этой задачи использовать математический подход DFS. Убедитесь, смогут ли ребята справиться с этой задачей.
Входные данные:
В первой сроке указано N – количество школьников, участников социальной сети и S - номер школьника, с которого начинается формирование «цепочки дружбы». Социальная сеть задан таблицей размером N на N, где N — количество школьников. Если два школьника дружат, то соответствующий элемент равен 1, иначе — 0. Нумерация школьников начинается с 1.
При обходе ближайших друзей их номера должны быть расположены в порядке возрастания, то есть, если 1 участник дружит непосредственно с участниками 4, 2 и 6, то надо обходить их в порядке 2, 4, 6.
Выходные данные:
Если построить единую «цепочку дружбы», чтобы она охватывала всех участников этой социальной сети, можно, то надо вывести в одну строку номера школьников в порядке их присоединения к этой цепочке.
Если такой возможности нет, то вывести слово НЕТ
| № | Входные данные | Выходные данные |
|
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
|
НЕТ
|