Вам дано неориентированное некорневое дерево — связный неориентированный граф без циклов.
Вы должны присвоить каждой вершине ненулевой целочисленный вес так, чтобы выполнялось следующее: если удалить любую вершину дерева, то все оставшиеся компоненты связности имеют одинаковую сумму весов в своих вершинах.
Выходные данные
Для каждого набора входных данных необходимо вывести одну строку с \(n\) целыми числами \(a_1, a_2, \ldots, a_n\), разделенными пробелами, где \(a_i\) — вес, присвоенный вершине \(i\). Веса должны удовлетворять \(-10^5 \leq a_i \leq 10^5\) и \(a_i \neq 0\).
Можно показать, что всегда существует решение, удовлетворяющее этим ограничениям. Если возможных решений несколько, выведите любое из них.
Примечание
В первом случае при удалении вершины \(1\) все оставшиеся компоненты связности имеют сумму весов \(5\), а при удалении вершины \(3\) все оставшиеся компоненты связности имеют сумму весов \(2\). При удалении других вершин остается только одна компонента связности, поэтому все оставшиеся компоненты связности имеют одинаковую сумму весов.
| № | Входные данные | Выходные данные |
|
1
|
2
5
1 2
1 3
3 4
3 5
3
1 2
1 3
|
-3 5 1 2 2
1 1 1
|