Statement : G. Statistics on Tree

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$.

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$.

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$.

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$.