\textit{Автор задачи: Даниил Орешников, разработчик: Степан Мишанин}
\vspace{0.2em}


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

Покажем теперь, как можно в нашем дереве найти гамильтонов путь, начинающийся в корне и заканчивающийся в одном из его детей. Решать эту задачу будем рекурсивно. Пусть сейчас мы рассматриваем вершину $v$, у которой имеется $k$ детей $u_1, u_2, u_3, ... u_k$. Будем по очереди рассматривать всех её детей, тогда у нас возможны два случая:
\begin{itemize}
  \item Если у рассматриваемой вершины $u_i$ есть дети, будем по очереди перемещаться в них (мы это можем сделать, так как расстояние между $v$ и любым ребёнком $u_i$ равно двум) и решать задачу рекурсивно для них. Напомним, что мы ищем гамильтонов цикл, начинающийся в корне и заканчивающийся в одном из его детей. Тогда, решив задачу для какого-то ребёнка $t_m$ вершины $u_i$, мы окажемся в каком-то из детей $t_m$ и можем из него переместиться в следующего ребёнка $u_i$, так как расстояние между ними будет равно трём. В конце остаётся только переместиться в вершину $u_i$, что также возможно, так как расстояние между $u_i$ и любым ребёнком её ребёнка равно двум.
  \item Если у рассматриваемой вершины $u_i$ нет детей, то добавим $u_i$ в ответ будто бы мы зашли в неё и продолжим рассматривать детей $v$. Тогда если у следующего ребёнка $u_j$ тоже нет детей, мы можем переместиться в него, так как расстояние между $u_i$ и $u_j$ равно двум, иначе~--- следуя описанному в первом пункте, мы переместимся в какого-то ребёнка $u_j$, что также возможно, так как расстояние между $u_i$ и ребёнком $u_j$ равно трём.
\end{itemize}

С помощью описанного способа найдем гамильтонов путь в нашем дереве. Так как он завершится в каком-то из детей корня, нам остаётся только переместиться из этого ребёнка в корень и мы получим требуемый в задаче цикл.