Цикл Потьомкіна

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

Звісно, вибір правильного маршруту потребує ретельного планування. Час від часу члени делегації відхиляються від запланованого маршруту для коротких інспекційних поїздок. Якщо вони повертаються на місце, яке вже відвідували, хитрість розкривається, оскільки вони побачать порожнє місце, де раніше було село. Щоб вразити делегацію, маршрут повинен включати щонайменше чотири ділянки.

Вам надається карта території Потьомкіна, яка містить список двонаправлених доріг між підходящими ділянками (перехрестя доріг обробляються складною системою шляхопроводів, що унеможливлює перехід з однієї дороги на іншу в будь-якій точці, окрім кінців). Князь Потьомкін попросив вас знайти таку послідовність s_1, ..., s_m ділянок, що:

• m \ge 4,

• всі ділянки різні (тобто s_i \ne s_j для всіх i \ne j),

• s_i безпосередньо з'єднаний з s_{i+1} дорогою для i = 1, \ldots, m - 1, s_m з'єднаний з s_1 дорогою,

• немає інших доріг серед ділянок у послідовності (тобто для всіх i < j таких, що j \ne i + 1 і або i \ne 1 або j \ne m, ділянки s_i і s_j не з'єднані дорогою).