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

На дворе уже стоит жаркий апрель, и Поликарп решил, что это самое лучшее время, чтобы разобрать поставленную несколько лет назад новогоднюю ёлку. Пока он ходил вокруг неё несколько часов, собираясь с силами, он обратил внимание, что ёлка по своей сути является деревом$$$^{\text{∗}}$$$, причём не обычным, а состоящим из нечётного числа вершин $$$n$$$. Также на $$$n-1$$$ вершине ёлки висят новогодние шарики $$$\frac{n-1}{2}$$$ цветов, причём в каждый из цветов покрашены ровно два каких-то шарика. На оставшейся вершине, как и полагается, находится навершие ёлки.

Наконец, спустя несколько дней моральной подготовки, Поликарп приступил к разборке ёлки. Первым делом он снял с неё навершие и уже начал разбирать отдельные ветви, когда вдруг задался вполне естественным вопросом: как можно удалить одно из рёбер его ёлки и перевесить шарики таким образом, чтобы сумма длин простых путей между шариками одного цвета была максимально возможной?

Под удалением ребра из дерева в задаче подразумевается следующая операция: выбрать пару смежных вершин $$$a$$$ и $$$b$$$ ($$$a \lt b$$$), после чего удалить из дерева вершину $$$b$$$ и подвесить за $$$a$$$ все смежные с $$$b$$$ вершины, кроме самой $$$a$$$.

Поликарп не может продолжить разбираться с ёлкой, пока не получит ответ на этот вопрос, однако на перебор всех возможных вариантов у него уйдёт ещё несколько лет. Поэтому, зная ваш опыт в олимпиадном программировании, он обратился за помощью к вам. Но справитесь ли вы с этой задачей?

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

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

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

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

В следующих $$$n-1$$$ строках идёт описание ёлки, заданное парами смежных вершин $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$).

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

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

Для каждого набора входных данных требуется вывести две строки.

В первой строке выведите пару вершин $$$u$$$, $$$v$$$, ребро между которыми Поликарпу предстоит удалить.

В следующей строке выведите массив $$$c$$$ из $$$n$$$ чисел от $$$0$$$ до $$$\frac{n-1}{2}$$$, где $$$c[i]$$$ — положительный номер цвета, присвоенного вершине $$$i$$$. Отметим, что $$$c[\text{max}(u, v)]= 0$$$, так как эту вершину мы удалили.

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

Рассмотрим первый набор входных данных.

Удалим ребро, соединяющее вершины $$$1$$$ и $$$2$$$. После этого вершина $$$2$$$ будет удалена из дерева, а вершины $$$3$$$ и $$$4$$$ будут соединены с вершиной $$$1$$$.

Раскрасим вершины $$$3$$$ и $$$4$$$ в первый цвет, а вершины $$$1$$$ и $$$5$$$ во второй. Сумма длин простых путей между шариками одного цвета равна $$$2 + 2 = 4$$$. Можно показать, что это значение является наибольшим из возможных.

Во втором и третьем примерах наибольшая сумма длин путей будет равна $$$3$$$ и $$$9$$$ соответственно.