Вам дано неориентированное некорневое дерево — связный неориентированный граф без циклов.
Вы должны присвоить каждой вершине ненулевой целочисленный вес так, чтобы выполнялось следующее: если удалить любую вершину дерева, то все оставшиеся компоненты связности имеют одинаковую сумму весов в своих вершинах.
Выходные данные
Для каждого набора входных данных необходимо вывести одну строку с \(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
|