Cerința

Se dă un arbore cu n noduri şi rădăcina r, nodurile fiind etichetate cu numerele de la 1 la n. Se cere să se afle pentru fiecare nod i, câte noduri din subarborele cu rădăcina i au eticheta mai mică decât i.

Date de intrare

Fișierul de intrare arbori_nr.in conține pe prima linie numerele n şi r, iar pe următoarele n-1 linii câte o pereche de numere u şi v, reprezentând faptul că între nodurile cu etichetele u şi v există o muchie.

Date de ieșire

Fișierul de ieșire arbori_nr.out va conține pe prima linie n numere naturale, al i-lea număr reprezentând numărul de noduri din subarborele cu eticheta i, ce au etichetele mai mici decât i.

Restricții și precizări

• 3 ≤ n ≤ 100.000
• 1 ≤ u,v ≤ n, distincte

Exemplu:

arbori_nr.in

5 2
2 3
5 4
5 1
2 5

arbori_nr.out

0 1 0 0 2 

Explicație

În arbore 1,3,4 sunt frunze, deci au câte 0 noduri în subarborii cu rădăcinile 1, 3 respectiv 5, 2 are în subarbore nodul 1 cu eticheta mai mică decât 2, 5 are în subarbore două noduri cu etichetele mai mici decât 5, nodurile 1 şi 4.