Se dă un arbore cu $N$ noduri (etichetate cu numere consecutive începand de la 1) cu rădăcina în nodul $1$, în care fiecare muchie are asociat un cost. Se defineşte un lanţ în jos în arbore ca fiind orice lanţ simplu ce uneşte un nod $A$ cu alt nod $B$ din subarborele lui $A$. Cu alte cuvinte, un lanţ în jos este un lanţ de la $A$ la $B$ în care $A$ este strămoş al lui B. Definim costul unui lanţ în jos ca fiind suma costurilor muchiilor din care este format lanţul.
Numim acoperire a unui arbore o partiţionare a muchiilor în lanţuri disjuncte, a căror reuniune este arborele iniţial. Regele Leonidas doreşte să acopere întreg arborele cu lanţuri în jos, însa are un număr limitat de lanţuri, notat în continuare cu $S$.

Se cere să se determine cel mai mic numar $K$ pentru care să existe o partiţionare completă a arborelui cu maxim $S$ lanţuri astfel încat costul fiecărui lanţ să fie cel mult $K$. Dacă nu există un astfel de $K$, să se afişeze $-1$.

Se cere să se determine cel mai mic numar $K$ pentru care să existe o partiţionare completă a arborelui cu maxim $S$ lanţuri astfel încat costul fiecărui lanţ să fie cel mult $K$. Dacă nu există un astfel de număr $K$, să se afişeze $-1$.

Pentru că şi tu vrei să lupţi alături de Leonidas pentru libertatea Spartei, trebuie să rezolvi această problemă ca să-ţi asiguri un loc în primii $300$ de spartani.
Leonidas este un rege înţelept. Ca să se asigure că nu vor exista Spartani care vor încerca să ghicească rezultatul, el vă cere să răspundeţi la $T$ astfel de probleme.

h2. Date de ieşire

Fişierul rege.out trebuie să conţină pe prima linie o singură valoare reală: media aritmetică a valorilor notate de Tudoraş.

Fişierul rege.out trebuie să conţină T linii: pe linia $i$ se află răspunsul pentru testul cu numarul $i$.

h2. Restricţii

{! problema/rege2?rege1resized.png !}

* 1-3 (cost 3)

* 1-4 (cost 3)

* 1-2-8 (cost 3)
* 8-9 (cost 3)
* 2-3-5-6 (cost 4)