Equal Tree Sums

Description:

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the number of vertices of the tree.

The next $$$n-1$$$ lines of each case contain each two integers $$$u, v$$$ ($$$1 \leq u,v \leq n$$$) denoting that there is an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

The sum of $$$n$$$ for all test cases is at most $$$10^5$$$.

Output:

For each test case, you must output one line with $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the weight assigned to vertex $$$i$$$. The weights must satisfy $$$-10^5 \leq a_i \leq 10^5$$$ and $$$a_i \neq 0$$$.

It can be shown that there always exists a solution satisfying these constraints. If there are multiple possible solutions, output any of them.

Sample Input:

2
5
1 2
1 3
3 4
3 5
3
1 2
1 3

Sample Output:

-3 5 1 2 2
1 1 1

Note:

In the first case, when removing vertex $$$1$$$ all remaining connected components have sum $$$5$$$ and when removing vertex $$$3$$$ all remaining connected components have sum $$$2$$$. When removing other vertices, there is only one remaining connected component so all remaining connected components have the same sum.