12781278 SUSTech Online Judge
Problem 1278 --Find the depth

1278: Find the depth

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 712  Solved: 218
[Submit][Status][Web Board]

Description

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.

Input

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.

Output

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

Sample Input

1
4
1 2
1 3
4 2

Sample Output

0 1 1 2

HINT

Source

 

[Submit][Status]