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