h2. Cerinţă

Dându-se un arbore cu $N$ noduri, să se afle numărul maxim de perechi de noduri înfrățite ale sale care se poate obține.

Dându-se un arbore cu $N$ noduri, să se afle numărul maxim de perechi de noduri înfrățite ale sale
care se poate obține.

h2. Date de intrare

Fișierul de intrare $tricolor.in$ va conține pe primul rând un număr natural nenul $T$ ce reprezintă numărul de teste. Urmează $T$ teste, fiecare test va descrie un arbore pentru care trebuie să se rezolve cerința. Pe primul rând al unui test apare un număr natural $N$ ce reprezintă numărul de noduri ale arborelui din testul respectiv. Pe următoarele $N-1$ rânduri vor apărea câte o pereche de numere întregi $x y$ separate printr-un spațiu, care indică existența unei muchii între nodul $x$ și nodul $y$.

Fișierul de intrare tricolor.in va conține pe primul rând un număr natural nenul $T$ ce reprezintă numărul de teste. Urmează $T$ teste, fiecare test va descrie un arbore pentru care trebuie să se rezolve
cerința. Pe primul rând al unui test apare un număr natural $N$ ce reprezintă numărul de noduri ale arborelui din testul respectiv. Pe următoarele $N-1$ rânduri vor apărea câte o pereche de numere întregi $x y$ separate printr-un spațiu, care indică existența unei muchii între nodul $x$ și nodul $y$.

h2. Date de iesire

Fișierul de ieșire $tricolor.out$ va conține $T$ rânduri. Fiecare rând va conține soluția pentru câte un test, în aceeași ordine ca în fișierul de intrare.

Fișierul de ieșire tricolor.out va conține $T$ rânduri. Fiecare rând va conține soluția pentru câte un test, în aceeași ordine ca în fișierul de intrare.

h2. Restricţii și precizări

* $1 ≤ T ≤ 10$

* $1 ≤ T ≤10$

* $1 ≤ N ≤ 5000$

* Într-un test oarecare, $1 ≤ x,y ≤ N, x ≠ y$
* Pentru $5$ puncte, $T = 1$ și $N ≤ 15$
* Pentru alte $10$ puncte, $T = 1$ și $N ≤ 20$

* Într-un test oarecare, $1 &le; x,y &le; N, <tex>x \neq y</tex>
* Pentru $5$ puncte, $T=1$ și $N &le; 15$
* Pentru alte $10$ puncte, $T=1$ și $N &le; 20$

* Pentru alte $5$ puncte, toți arborii descriși au exact $2$ frunze și $N  ≤ 500$
* Pentru alte $10$ puncte, pentru toți arborii descriși există exact două noduri ale arborelui de care se leagă toate frunzele, situate la capetele unui lanț elementar și $N  ≤ 500$.
* Pentru alte $50$ de puncte, $N ≤ 500$

 1
|

h2. Explicatie
 
Este optim sa coloram, in primul exemplu, astfel:
 
!problema/tricolor?b.png!
 
Ce duce la 7 perechi de noduri înfrățite.
 

== include(page="template/taskfooter" task_id="tricolor") ==