Fişierul intrare/ieşire:	tricolor.in, tricolor.out	Sursă	ONI 2018, clasele 11-12, ziua 1
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.8 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Tricolor

Tanaka are un arbore (un tri) cu N noduri numerotate de la 1 la N. El vrea să coloreze nodurile arborelui în alb sau negru astfel încât numărul de perechi (neordonate) de noduri înfrățite să fie maxim. Două noduri sunt înfrățite dacă și numai dacă ambele sunt albe și fie sunt legate direct printr-o muchie, fie lanțul elementar unic dintre ele conține doar noduri negre.

Cerinţă

Dându-se un arbore cu N noduri, să se afle numărul maxim de perechi de noduri înfrățite ale sale care se poate obține.

Date de intrare

Fișierul de intrare tricolor.in va conține pe primul rând un număr natural nenul T ce reprezintă numărul de teste. Urmează T teste, fiecare test va descrie un arbore pentru care trebuie să se rezolve cerința. Pe primul rând al unui test apare un număr natural N ce reprezintă numărul de noduri ale arborelui din testul respectiv. Pe următoarele N-1 rânduri vor apărea câte o pereche de numere întregi x y separate printr-un spațiu, care indică existența unei muchii între nodul x și nodul y.

Date de iesire

Fișierul de ieșire tricolor.out va conține T rânduri. Fiecare rând va conține soluția pentru câte un test, în aceeași ordine ca în fișierul de intrare.

Restricţii și precizări

1 ≤ T ≤ 10
1 ≤ N ≤ 5000
Într-un test oarecare, 1 ≤ x,y ≤ N, x ≠ y
Pentru 5 puncte, T = 1 și N ≤ 15
Pentru alte 10 puncte, T = 1 și N ≤ 20
Pentru alte 5 puncte, toți arborii descriși au exact 2 frunze și N ≤ 500
Pentru alte 10 puncte, pentru toți arborii descriși există exact două noduri ale arborelui de care se leagă toate frunzele, situate la capetele unui lanț elementar și N ≤ 500.
Pentru alte 50 de puncte, N ≤ 500
Pentru alte 20 de puncte, nu există restricții suplimentare.