D. Удаление рёбер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Далее следуют $$$n-1$$$ строка. $$$i$$$-я из них содержит два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$) — концы $$$i$$$-го ребра. Гарантируется, что описанный граф является деревом.

Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «NO», если невозможно удалить все ребра.

В противном случае выведите «YES» и в следующих $$$n-1$$$ строке выведите возможный порядок удаления ребер. Для каждого ребра выведите его концы в любом порядке.

Пример
Входные данные
5
2
1 2
3
1 2
2 3
4
1 2
2 3
3 4
5
1 2
2 3
3 4
3 5
7
1 2
1 3
2 4
2 5
3 6
3 7
Выходные данные
YES
2 1
NO
YES
2 3
3 4
2 1
YES
3 5
2 3
2 1
4 3
NO
Примечание

Пример $$$1$$$: можно удалить данное ребро, поскольку оно не смежно никакому ребру.

Пример $$$2$$$: оба ребра смежны ровно одному ребру, поэтому невозможно удалить ни одно из них. Таким образом, ответ «NO».

Пример $$$3$$$: ребро $$$2-3$$$ смежно двум другим ребрам, поэтому его можно удалить. После этого также становится возможным удалить оставшиеся ребра.