e-olymp
Məsələlər

Цикл Потемкина

Цикл Потемкина

Князь Потемкин известен своими потешными деревнями, созданными на скорую руку, чтобы произвести впечатление на приезжих сановников. Князь будет вести делегацию по замкнутому маршруту своей территории, и на каждом подходящем участке группа актеров будет строить мобильную деревню и притворяться ее жителями. Как только делегация уедет, актеры разбирали деревню и шли вперед делегации на следующий подходящий участок.

Конечно, выбор правильного маршрута требует некоторых размышлений. Члены делегации время от времени покидают запланированный маршрут для коротких инспекционных поездок, и если они когда-либо возвращаются на место, которое ранее посещали, то уловка не удавалась, поскольку они увидят пустое место, где ранее видели деревню. Чтобы произвести впечатление на делегацию, маршрут должен пройти как минимум через четыре участка.

Вам предоставляется карта территории Потемкина, в том числе список двунаправленных дорог между подходящими участками (пересечения дорог обрабатываются сложной системой путепроводов, в результате чего высокопоставленные лица не могут переходить с одной дороги на другую ни в какой из точек кроме концов). Князь Потемкин попросил Вас найти такую последовательность s1, ..., sm участков, что:

  • m4,
  • все участки различны (то есть sisj для всех ij),
  • si непосредмтвенно соединен с si+1 дорогой для i = 1, ..., m - 1, sm соединен с s1 дорогой,
  • нет других дорог среди участков в последовательности (то есть для всех i < j таких что ji + 1 и или i1 или jm, участки si и sj не соединены дорогой).

Входные данные

Первая строка содержит два целых числа n и r (0n1000, 0r105) - количество участков и дорог. i-ая из следующих r строк содержит два целых числа ai и bi (1ai, bin), означающие что участки ai и bi соединены дорогой. Каждые два участка соединены не более чем одной дорогой.

Выходные данные

Выведите последовательность s1, ..., sm попарно различных целых чисел, описывающих искомый маршрут (любой, если таковых имеется несколько). Если такой последовательности не существует, выведите "no".

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5 6
1 2
1 3
2 3
4 3
5 2
4 5
Çıxış verilənləri #1
2 5 4 3
Giriş verilənləri #2
4 5
1 2
2 3
3 4
4 1
1 3
Çıxış verilənləri #2
no
Mənbə 2015 CEOI День 1, Задача A