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