Пытаясь спасти своего друга, Уэнсдей оказывается в Лабиринте Кошмаров, созданном древним проклятием. Структура лабиринта представляет собой дерево из $n$ комнат и $n-1$ коридоров между ними. Каждая комната имеет уникальный номер от $1$ до $n$.

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

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