Вам дано дерево$$$^{\text{∗}}$$$ с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Вы можете изменить его структуру, используя следующую многошаговую операцию, называемую скользящей операцией:
Например, на рисунке ниже иллюстрируется эта операция с $$$a = 4$$$, $$$b = 3$$$ и $$$c = 5$$$ в самом левом дереве.
Можно доказать, что после скользящей операции полученный граф по-прежнему является деревом.
Ваша задача состоит в том, чтобы найти последовательность скользящих операций, которая преобразует дерево в бамбук$$$^{\text{†}}$$$, при этом минимизируя общее количество операций. Вам нужно вывести только первую скользящую операцию в оптимальной последовательности, если требуется хотя бы одна операция. Можно доказать, что возможно преобразовать дерево в бамбук, используя конечное количество операций.
$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.
$$$^{\text{†}}$$$Бамбук — это дерево, в котором каждая вершина имеет степень не более $$$2$$$. Обратите внимание, что граф с только $$$1$$$ вершиной и без рёбер также является бамбуком.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.
$$$i$$$-я из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — концы $$$i$$$-го ребра.
Гарантируется, что заданные рёбра образуют дерево.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных:
Если есть несколько допустимых вариантов для первой операции, вы можете вывести любой из них.
464 33 53 11 23 6121 255 42 34 21 4
4 3 5 -1 -1 2 4 1
Первый набор входных данных соответствует примеру, приведенному в условии задачи. Можно доказать, что мы не можем преобразовать данное дерево в бамбук, используя менее чем $$$2$$$ операции.
Преобразовать данное дерево в бамбук, используя $$$2$$$ операции, можно так: сначала мы выполняем операцию с $$$a=4$$$, $$$b=3$$$ и $$$c=5$$$, как показано в примере. Затем мы применяем операцию с $$$a=3$$$, $$$b=5$$$ и $$$c=6$$$. После этого дерево становится бамбуком. Вторая операция иллюстрируется на рисунке ниже.
Таким образом, мы получаем последовательность скользящих операций с минимальным общим количеством операций. Обратите внимание, что в выводе должна быть только первая операция; количество операций и вторая операция не должны появляться в выводе.
Во втором и третьем наборах входных данных дерево уже является бамбуком, поэтому операции не требуются.
| Codeforces Round 1045 (Div. 2) |
|---|
| Закончено |
