Сестры Анна и Эльза из мультфильма "Холодное Сердце" отправляются в путешествие по городам своего королевства, чтобы восстановить зимнюю погоду и найти своих друзей. Во время путешествия они должны собирать магические кристаллы, которые хранятся в каждом городе королевства. Чтобы побывать единожды во всех городах королевства сестры используют заветное правило 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
|
НЕТ
|