Задан связный неориентированный граф $$$G$$$, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Вершины пронумерованы от $$$1$$$ до $$$n$$$. Также задано дерево $$$T$$$, состоящее из тех же $$$n$$$ вершин. Все ребра дерева $$$T$$$ являются ребрами графа $$$G$$$.

Назовем списком смежности вершины $$$v$$$ список таких вершин $$$u$$$, что существует ребро $$$(v, u)$$$. В каждом списке смежности вершины расположены в каком-то порядке.

Напомним классический алгоритм обхода в глубину графа $$$G$$$. Определим функцию dfs, которая принимает один целочисленный аргумент $$$v$$$ — номер рассматриваемой вершины. На входе в функцию вершина $$$v$$$ помечается посещенной. Затем перебираются все вершины $$$u$$$ списка смежности $$$v$$$. Если $$$u$$$ ранее была посещена, то алгоритм переходит к рассмотрению следующей вершины в списке смежности. Если же $$$u$$$ не была посещена, то функция dfs запускается из вершины $$$u$$$ рекурсивно. Когда рекурсивный вызов завершается, алгоритм снова переходит к рассмотрению следующей вершины в списке смежности. Когда следующей вершины в списке смежности нет, функция завершается.

Дерево обхода в глубину строится следующим образом. Когда функция dfs находится в вершине $$$v$$$ и запускается рекурсивно из вершины $$$u$$$, ребро $$$(v, u)$$$ добавляется в дерево. Можно показать, что граф, построенный таким алгоритмом, действительно является деревом.

Для каждой вершины $$$i$$$ от $$$1$$$ до $$$n$$$ определите, можно ли так переупорядочить списки смежности всех вершин (возможно, не изменяя порядок), чтобы дерево обхода в глубину графа $$$G$$$, запущенного из вершины $$$i$$$, состояло из тех же ребер, что и дерево $$$T$$$. Обратите внимание: вы можете менять порядок вершин внутри каждого списка смежности, но не можете перемещать их между разными списками смежности.