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$

Este optim sa coloram, in primul exemplu, astfel:

!problema/tricolor/b.png

!problema/tricolor?b.png!
 
Ce duce la 7 perechi de noduri înfrățite.

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