Grarbore

Bossanip și Henry au un arbore $A$ cu $N$ noduri. Ei se întreabă, pentru fiecare valoare $k$ cuprinsă între $1$ și $N-1$, care este numărul de subarbori ai lui $A$ pentru care gradul maxim al unui nod din subarbore este egal cu $k$. Un subarbore se definește ca fiind o submulțime conexă de noduri și muchii din arborele $A$. Gradul unui nod dintr-un subarbore se definește ca numărul de vecini pe care îi are acel nod în subarbore (NU în arborele $A$).

Date de intrare

Fişierul de intrare grarbore.in va conține pe prima linie un număr natural $T$, semnificând numărul de arbori din fișierul de intrare. Pe liniile următoare se vor afla descrierile celor $T$ arbori. Descrierea celui de-al $i$-lea arbore va conține pe prima linie numărul natural $N_i$, semnificând dimensiunea celui de-al $i$-lea arbore. Pe următoarele $N_i – 1$ linii, se vor afla $N_i – 1$ perechi de numere $a$ și $b$, semnificând că al $i$-lea arbore conține muchia $(a, b)$.

Date de ieşire

În fişierul de ieşire grarbore.out veți afișa $T$ linii. Pe a $i$-a dintre acestea veți afișa $N_i – 1$ valori, a $k$-a dintre acestea fiind egală cu numărul de subarbori ai celui de-al $i$-lea arbore pentru care gradul maxim al unui nod din subarbore este exact $k$.

Restricţii si precizări

• $T \leq 5$

• $1 \leq N_i \leq 500$.

• Nodurile sunt numerotate de la $0$.

• Pentru 60% dintre teste $n \leq 250$

• Pentru 10% dintre teste $n \leq 10$

Exemplu

grarbore.in

1
5
0 1
0 2
1 3
1 4

grarbore.out

4 6 2 0

Explicatie

Există $4$ arbori pentru care gradul maxim al unui nod este $1$, formați din submulțimile de noduri $(0, 1)$, $(0, 2)$, $(1, 3)$, $(1, 4)$.

Există $6$ arbori pentru care gradul maxim al unui nod este $2$, formați din submulțimile de noduri $(0, 1, 2)$, $(0, 1, 3)$, $(0, 1, 4)$, $(1, 3, 4)$, $(0, 1, 2, 3)$, $(0, 1, 2, 4)$.

Există $2$ arbori pentru care gradul maxim al unui nod este $3$, formați din submulțimile de noduri $(0, 1, 3, 4)$, $(0, 1, 2, 3, 4)$.

Nu există niciun arbore pentru care gradul maxim al unui nod este $4$.