Given a tree with N nodes and N-1 edges, the length of each edge is 1, the root of the tree is node 1, please find the depth of all nodes. the depth for node 1 is 0.

The first line will be a integer T \((1 \leq T \leq 10)\), which is the number of test cases. 
For each test data: 
The first line contains an integer N \((1 \leq N \leq 10^5 )\) — the number of nodes.
the next N-1 lines contain two integers a and b \((1 \leq a,b \leq N)\), which means there is an edge between node a and b.

For each case, print one line with N integers, the i-th integer indicates the depth of node i. 

1
4
1 2
1 3
4 2

0 1 1 2