Цикл Потемкина
Цикл Потемкина
Князь Потемкин известен своими потешными деревнями, созданными на скорую руку, чтобы произвести впечатление на приезжих сановников. Князь будет вести делегацию по замкнутому маршруту своей территории, и на каждом подходящем участке группа актеров будет строить мобильную деревню и притворяться ее жителями. Как только делегация уедет, актеры разбирали деревню и шли вперед делегации на следующий подходящий участок.
Конечно, выбор правильного маршрута требует некоторых размышлений. Члены делегации время от времени покидают запланированный маршрут для коротких инспекционных поездок, и если они когда-либо возвращаются на место, которое ранее посещали, то уловка не удавалась, поскольку они увидят пустое место, где ранее видели деревню. Чтобы произвести впечатление на делегацию, маршрут должен пройти как минимум через четыре участка.
Вам предоставляется карта территории Потемкина, в том числе список двунаправленных дорог между подходящими участками (пересечения дорог обрабатываются сложной системой путепроводов, в результате чего высокопоставленные лица не могут переходить с одной дороги на другую ни в какой из точек кроме концов). Князь Потемкин попросил Вас найти такую последовательность s1
, ..., sm
участков, что:
- m ≥ 4,
- все участки различны (то есть
si
≠sj
для всех i ≠ j), si
непосредмтвенно соединен сsi+1
дорогой для i = 1, ..., m - 1,sm
соединен сs1
дорогой,- нет других дорог среди участков в последовательности (то есть для всех i < j таких что j ≠ i + 1 и или i ≠ 1 или j ≠ m, участки
si
иsj
не соединены дорогой).
Входные данные
Первая строка содержит два целых числа n и r (0 ≤ n ≤ 1000, 0 ≤ r ≤ 105
) - количество участков и дорог. i-ая из следующих r строк содержит два целых числа ai
и bi
(1 ≤ ai
, bi
≤ n), означающие что участки ai
и bi
соединены дорогой. Каждые два участка соединены не более чем одной дорогой.
Выходные данные
Выведите последовательность s1
, ..., sm
попарно различных целых чисел, описывающих искомый маршрут (любой, если таковых имеется несколько). Если такой последовательности не существует, выведите "no".
5 6 1 2 1 3 2 3 4 3 5 2 4 5
2 5 4 3
4 5 1 2 2 3 3 4 4 1 1 3
no