Пусть $$$u$$$ и $$$v$$$ — две различные вершины в некотором ориентированном графе. Назовем упорядоченную пару $$$(u, v)$$$ хорошей, если существует путь из вершины $$$u$$$ в вершину $$$v$$$ по дугам данного графа.
Вам задано неориентированное дерево из $$$n$$$ вершин и $$$n - 1$$$ ребра. Определите, возможно ли выбрать направление для каждого ребра этого дерева так, чтобы количество хороших пар в нем стало строго равно $$$n$$$. Если это возможно, выведите любой способ ориентировать ребра так, чтобы количество хороших пар было равно $$$n$$$.
Одна из возможных ориентированных версий дерева для первого набора входных данных. В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют сами наборы.
В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.
В следующих $$$n - 1$$$ строках заданы описания ребер. В $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — вершины, которые соединяет $$$i$$$-е ребро.
Гарантируется, что ребра в каждом наборе входных данных действительно образуют неориентированное дерево и что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «NO» (регистр не важен), если невозможно ориентировать все ребра дерева и получить ровно $$$n$$$ хороших пар вершин.
В противном случае выведите «YES» (регистр не важен) и далее выведите $$$n - 1$$$ пару чисел $$$u_i$$$ и $$$v_i$$$ через пробел — сами ребра, ориентированные от $$$u_i$$$ к $$$v_i$$$.
Ребра можно выводить в произвольном порядке. Если существует несколько ответов, выведите любой.
451 22 41 33 551 21 31 44 522 143 11 22 4
YES 1 2 3 1 3 5 4 2 YES 2 1 3 1 4 1 5 4 NO YES 1 3 2 1 2 4
Дерево из первого набора входных данных и его возможная ориентированная версия представлены в условии задачи. В данной версии ровно $$$5$$$ хороших пар вершин: $$$(3, 5)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$, $$$(1, 2)$$$ и $$$(4, 2)$$$.
Одна из возможных ориентированных версий дерева из второго набора приведена ниже:
В представленном ответе ровно $$$5$$$ хороших пар вершин: $$$(2, 1)$$$, $$$(3, 1)$$$, $$$(4, 1)$$$, $$$(5, 4)$$$ и $$$(5, 1)$$$.
В третьем наборе всего две ориентированные пары вершин, но для любого из направлений ребра только одна пара будет хорошей.
