CTree
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ță)
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
.
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ă.
1 ≤ N ≤ 300 000
0 ≤ i ≤ N − 2
și \(X_i ≠ Y_i\).1 ≤ T ≤ 300 000
.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
Pentru primul exemplu:
0
poate fi numit capitală fără a efectua modificări.1
, se distruge drumul (0, 2)
și se construiește drumul (1, 2)
.2
, se distruge drumul (0, 1)
și se construiește drumul (1, 2)
.ID: 93
Upload: liviu
Input: Console Input
Memory limit: 128MB/128MB
Time limit: 0.55s
Author: Bogdan Sitaru
Source: Lot 2021 Baraj 1 Seniori: Problema 3