给你一个无向无根树,即没有循环的连通无向图。
您必须为每个顶点分配一个非零整数权重,以便满足以下条件:如果删除树的任何顶点,则每个剩余的连接组件在其顶点中具有相同的权重总和。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$。
可以证明,总是存在满足这些约束的解。如果有多种可能的解决方案,则输出其中任何一个。
示例
输入 #1
2 5 1 2 1 3 3 4 3 5 3 1 2 1 3
输出 #1
-3 5 1 2 2 1 1 1
注意
在第一种情况下,当删除顶点 $$$1$$$ 时,所有剩余的连接组件的总和为 $$$5$$$,而当删除顶点 $$$3$$$ 时,所有剩余的连接组件的总和为 $$$2$$$。删除其他顶点时,只有一个剩余的连通分量,因此所有剩余的连通分量具有相同的总和。