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

* $1 ≤ T ≤ 10$

* $1 ≤ T ≤ 5$

* $1 ≤ N, S ≤ 100 000$
* $1 ≤ Costul oricărei muchii ≤ 10 000$

Avem T = 2 teste.
Pentru primul test, avem un arbore cu $N = 10$ noduri. Dorim să acoperim arborele cu maxim $S = 6$ lanţuri. Arborele se poate acoperi cu următoarele lanţuri:

{!< problema/rege2?rege1resized.png !}
* 1-3 (cost 3)

{! problema/rege2?rege1resized.png !}
 
* 1-4 (cost 3)

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

Sunt exact $6$ lanţuri (maxim $6$ avem voie), iar costul cel mai mare al unui lanţ e $4$. Nu se poate face o acoperire cu cost maxim mai mic cu cel mult $6$ lanţuri.
Pentru cel de-al doilea test, arborele are N = 6 noduri si dorim să-l acoperim cu maxim 4 lanţuri. Arborele se poate acoperi cu urmatoarele lanţuri:

{!< problema/rege2?rege2resized.png !}

{! problema/rege2?rege2resized.png !}

* 1-2 (cost 4)
* 2-3 (cost 3)