* Dacă între două noduri $X$ şi $Y$ există *muchie* în arbore, atunci distanţa dintre punctele asociate acestor noduri *trebuie* să fie egală cu costul muchiei dintre ele.
* Distanţa maximă dintre două puncte asociate nodurilor trebuie să fie minimă.

Voi trebuie sa gasiti aceasta distanta minima.
 

h2. Date de intrare
Fişierul de intrare $oxificare.in$ va conţine pe prima sa linie valoarea întreagă $T$, reprezentând numărul de teste din fişier. Structura unui test este următoarea:

h2. Date de ieşire

În fişierul de ieşire $oxificare.out$ se va afla o singura valoare, reprezentând distanţa maximă minim posibilă în cazul unei liniarizări optime a arborelui.

În fişierul de ieşire $oxificare.out$ se vor afla $T$ linii, a $i$-a linie reprezentand solutia pentru testul $i$.

h2. Restricţii