E. Одинаковые суммы деревьев
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано неориентированное некорневое дерево — связный неориентированный граф без циклов.

Вы должны присвоить каждой вершине ненулевой целочисленный вес так, чтобы выполнялось следующее: если удалить любую вершину дерева, то все оставшиеся компоненты связности имеют одинаковую сумму весов в своих вершинах.

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

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

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

Следующие $$$n-1$$$ строк каждого случая содержат по два целых числа $$$u, v$$$ ($$$1 \leq u,v \leq n$$$), обозначающих наличие ребра между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

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

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

Для каждого набора входных данных необходимо вывести одну строку с $$$n$$$ целыми числами $$$a_1, a_2, \ldots, a_n$$$, разделенными пробелами, где $$$a_i$$$ — вес, присвоенный вершине $$$i$$$. Веса должны удовлетворять $$$-10^5 \leq a_i \leq 10^5$$$ и $$$a_i \neq 0$$$.

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

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

В первом случае при удалении вершины $$$1$$$ все оставшиеся компоненты связности имеют сумму весов $$$5$$$, а при удалении вершины $$$3$$$ все оставшиеся компоненты связности имеют сумму весов $$$2$$$. При удалении других вершин остается только одна компонента связности, поэтому все оставшиеся компоненты связности имеют одинаковую сумму весов.