N. Maximize Minimum Mex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected tree with $$$n$$$ vertices, labeled from $$$0$$$ to $$$n-1$$$. The tree has $$$n-1$$$ edges and is connected and acyclic.

Your task is to select exactly $$$k$$$ vertices ($$$2 \leq k \leq n$$$) such that the minimum $$$\operatorname{MEX}$$$ value over all paths between two chosen vertices is maximized.

For any two vertices $$$u$$$ and $$$v$$$, define $$$P_{uv}$$$ as the set of vertex labels that appear on the unique simple path between them. The function $$$\operatorname{MEX}(P_{uv})$$$ is defined as the smallest non-negative integer that does not appear in $$$P_{uv}$$$.

Formally, for a chosen set of vertices $$$S$$$ with $$$|S| = k$$$, we define: $$$$$$ f(S) = \min_{u, v \in S, u \neq v} \operatorname{MEX}(P_{uv}). $$$$$$

Your goal is to maximize $$$f(S)$$$ over all valid choices of $$$S$$$.

For each integer $$$k$$$ from $$$2$$$ to $$$n$$$, compute the maximum possible value of $$$f(S)$$$.

Input

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

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

The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(0 \leq u, v \lt n)$$$, representing an undirected edge between nodes $$$u$$$ and $$$v$$$.

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

Output

For each test case, print $$$n-1$$$ integers. The $$$i$$$-th integer should represent the maximum possible value of the minimum $$$\operatorname{MEX}$$$ when choosing $$$k = i+1$$$ nodes.

Example
Input
1
5
0 1
1 3
1 4
0 2
Output
4 1 0 0
Note

The given tree has $$$n = 5$$$ nodes with the following structure:

  • Node $$$0$$$ is connected to nodes $$$1$$$ and $$$2$$$.
  • Node $$$1$$$ is connected to nodes $$$3$$$ and $$$4$$$.

For different values of $$$k$$$:

  • For $$$k = 2$$$, selecting nodes $$$\{2, 3\}$$$ maximizes $$$f(S)$$$, yielding $$$\operatorname{MEX}(\mathcal{P}_{2,3}) = 4$$$.
  • For $$$k = 3$$$, selecting nodes $$$\{0, 1, 2\}$$$ yields a maximum $$$f(S) = 1$$$.
  • For $$$k = 4$$$ and $$$k = 5$$$, the maximum value of $$$f(S)$$$ is $$$0$$$.