G. Statistics on Tree
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Nanatsukaze - Aria

You are given a tree of $$$n$$$ vertices. We define the value of a pair $$$(u,v)$$$ ($$$1\leq u\leq v\leq n$$$) as the size of the largest component after removing all edges on the path from $$$u$$$ to $$$v$$$ in the original tree.

For every $$$1\leq i\leq n$$$, you have to find the number of pairs $$$(u,v)$$$ satisfying that its value is $$$i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n \leq 10^5$$$) — the number of vertices.

Then $$$n-1$$$ lines follow, the $$$i$$$-th line containing two integers $$$u$$$ and $$$v$$$ ($$$1\leq u,v\leq n$$$) — the two vertices that the $$$i$$$-th edge connects.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers, the $$$i$$$-th of which denotes the number of distinct pairs $$$(u,v)$$$ satisfying its value is $$$i$$$.

Example
Input
7
1
2
1 2
3
1 2
1 3
4
1 2
2 3
3 4
5
1 2
2 3
2 4
2 5
7
3 4
1 5
2 3
2 6
5 2
7 3
8
2 1
3 2
4 1
5 3
6 2
7 6
8 1
Output
1 
1 2 
1 2 3 
1 3 2 4 
0 0 6 4 5 
0 4 5 5 3 4 7 
0 0 12 4 3 5 4 8
Note

In the first test case, the value of pair $$$(1, 1)$$$ is $$$1$$$.

In the second test case, the values of pairs $$$(1, 1)$$$ and $$$(2, 2)$$$ are both $$$2$$$, because no edges will be removed. The value of pair $$$(1, 2)$$$ is $$$1$$$, because edge $$$(1, 2)$$$ is on the path from $$$1$$$ to $$$2$$$ in the tree, and after removing it, there will be $$$2$$$ components left, which are $$$\{1\}$$$ and $$$\{2\}$$$, and the size of the largest component is $$$1$$$.

In the sixth test case, the value of pair $$$(4, 6)$$$ is $$$3$$$, because edges $$$(3, 4)$$$, $$$(2, 3)$$$, and $$$(2, 6)$$$ are on the path from $$$4$$$ to $$$6$$$ in the tree, and after removing them, there will be $$$4$$$ components left, which are $$$\{1, 2, 5\}$$$, $$$\{3, 7\}$$$, $$$\{4\}$$$, and $$$\{6\}$$$, and the size of the largest component is $$$3$$$.