Renumiți pentru admirația lor pentru boabele de cacao, aztecii s-au hotărât să le depoziteze în capitala imperiului. Imperiul Aztec este format din N orașe (numerotate de la 0 la N − 1), legate prin N − 1 drumuri, astfel încât se poate ajunge din orice oraș în altul parcurgând unul sau mai multe drumuri.
Un oraș poate fi numit capitală doar dacă, în urma distrugerii tuturor drumurilor adiacente acestui oraș, orice mulțime conectată (pentru care oricum am alege 2 orașe, se poate ajunge din primul în cel de-al doilea prin drumuri) are cel mult \(\frac{N}{2}\) orașe.

Arhitectul șef al aztecilor se gândește să schimbe structura drumurilor din imperiu. Astfel, el poate efectua următoarea operație (posibil de mai multe ori): distruge un drum și construiește unul nou, astfel încât imperiul să rămână conectat.
Arhitectul nu știe încă în ce oraș este cel mai sigur să depoziteze boabele, însă ar vrea să găsească pentru fiecare oraș de la 0 la N − 1 care este numărul minim de operații ce trebuiesc efectuate astfel încât acesta poate fi numit capitală. (Aztecii își pot schimba capitala, atât timp cât boabele lor sunt în siguranță)

Date de intrare

Pe prima linie se va găsi T, numărul de scenarii. Urmează apoi T grupe de linii, fiecare descriind câte un scenariu de rezolvat. Pe prima linie a unui scenariu se află N cu semnificația din enunț. Pe următoarele N - 1 linii urmează două numere x și y separate prin spații, avanâd semnificația că există un drum între x și y.

Date de ieșire

Se vor afișa T linii, fiecare formată din N numere separate prin spații, pentru fiecare i de la 0 la N − 1 numărul minim de operații necesare pentru ca orașul i să poată fi numit capitală.

Restricții și precizări

• 1 ≤ N ≤ 300 000
• \(0 ≤ X_i, Y_i ≤ N − 1\) pentru 0 ≤ i ≤ N − 2 și \(X_i ≠ Y_i\).
• Fie \(S_N\) suma N-urilor pentru toate scenariile. \(1 ≤ S_N ≤ 300 000\).
• 1 ≤ T ≤ 300 000.
• Se poate observa că pentru o configurație a drumurilor pot exista mai multe orașe ce pot fi capitală în același timp.

Subtask 1 (7 puncte)

• \(1 ≤ S_N ≤ 10\)

Subtask 2 (14 puncte)

• \(1 ≤ S_N ≤ 50\)

Subtask 3 (17 puncte)

• \(1 ≤ S_N ≤ 200\)

Subtask 4 (21 de puncte)

• \(1 ≤ S_N ≤ 2 000\)

Subtask 5 (18 puncte)

• \(1 ≤ S_N ≤ 40 000\)

Subtask 6 (23 de puncte)

• Fără restricții suplimentare.

Exemplu

stdin

2
3
0 2
0 1
7
1 0
1 2
2 3
3 4
5 1
1 6

stdout

0 1 1
1 0 1 2 2 1 1

Explicații

Pentru primul exemplu:

• Orașul 0 poate fi numit capitală fără a efectua modificări.
• Pentru orașul 1, se distruge drumul (0, 2) și se construiește drumul (1, 2).
• Pentru orașul 2, se distruge drumul (0, 1) și se construiește drumul (1, 2).