Problem A: Distance in the country

Problem A: Distance in the country

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 56  Solved: 30
[Submit][Status][Web Board]

Description

There are \(n\) cities in the country with \(n-1\) roads connecting them. In other words, the country can be represented as a tree. Pisces is now in city \(1\), and he wants to know the distance from his current position to each of the other cities. Here the distance between cities \(A\) and \(B\) is defined as the number of roads in the simple path (a path without duplicate cities) from \(A\) to \(B\).

Input

The first line contains an interger \(T(1\leq T\leq 10)\), which represents the number of test cases.

For each of the test case, the first line contains an integer \(n(1\leq n\leq 10^4)\), which is the number of cities. Each of the next \(n-1\) lines contains \(2\) interger \(u\) and \(v(1\leq u, v\leq n)\), representing that there is a road from city \(u\) to city \(v\).

Output

For each test case, print \(n\) integers. The \(i\)-th interger represents the distance from city \(1\) to city \(i\). Especially, the distance of city \(1\) itself is \(0\).

Sample Input

1
5
1 2
1 3
2 4
4 5

Sample Output

0 1 1 2 3

HINT

[Submit][Status]