Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

DFS medyje

Duotas šakninis medis - jungus beciklis grafas, kurį sudaro N viršūnių ir N-1 briaunų. Medžio šaknis yra viršūnė 1.

Kiekvienai medžio viršūnei v jums reikia rasti tris dalykus:

  • kas yra viršūnės v tėvinė viršūnė;
  • koks yra viršūnės v gylis (tai yra, atstumas iki šaknies);
  • kiek vaikų turi viršūnė v.

Įvestis

Pirmoje eilutėje pateiktas natūralusis skaičius n (1\\leqn\\leq10^5) - viršūnių skaičius medyje.

Toliau pateiktos n-1 eilučių, kuriose pateikta po du skaičius u ir v (1\\lequ,v\\leqn), kurie reiškia, kad medyje yra briauna tarp viršūnių u ir v.

Išvestis

Išveskite n eilučių, kur i-tojoje jų būtų trys skaičiai: i-tosios viršūnės tėvinė viršūnė, i-tosios viršūnės gylis ir vaikų skaičius.

Pastaba. Kadangi viršūnė 1 yra šaknis, tai tėvinės viršūnės ji neturi - vietoj jos tėvinės viršūnės išveskite tiesiog skaičių 0 (žr. pavyzdžius).

Pavyzdžiai

Duomenys Rezultatai Paaiškinimai 
6
3 5
3 1
1 4
6 3
3 2
 
0 0 2
3 2 0
1 1 3
1 1 0
3 2 0
3 2 0
 
Medis atrodo taip: 
pavyzdys