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