E. Restricted Diameter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an undirected tree with $$$N$$$ nodes and $$$N-1$$$ edges, we define restricted diameter for a node $$$i$$$ as maximum distance path between any $$$2$$$ nodes(among all possible combinations) such that path between them contains node $$$i$$$.

For each node $$$i$$$ $$$(1 \leq i \leq N)$$$ print the restricted diameter length.

Input

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

First line of each test case contains an integers $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ - number of vertices in tree.

Next $$$N-1$$$ line describe the edges of the tree. The $$$i^{th}$$$ of these $$$N-1$$$ lines contains two space separated integers $$$u_i$$$ and $$$v_i$$$ denoting an edge between $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i,v_i \leq N)$$$.

(The sum of $$$N$$$ over all testcases won't exceed $$$10^5$$$).

Output

A line containing $$$n$$$ integers denoting restricted diameter length for node $$$i$$$ $$$(1 \leq i \leq N)$$$.

Example
Input
2
4
1 2
2 3
2 4
8
1 2
2 3
1 4
1 5
4 6
4 7
7 8
Output
2 2 2 2 
5 5 5 5 4 4 5 5
Note
Centered unscaled image.

Given above is a graph of test case $$$2$$$. Clearly the diameter of the graph is $$$5$$$. So every node of the diameter is having the restricted diameter equal to $$$5$$$. For nodes $$$5$$$ and $$$6$$$, the restricted diameter is $$$4$$$.