== include(page="template/taskheader" task_id="pisici") ==

Se dă un arbore cu $N &ge; 2$ noduri şi probabilităţi $p$ pe muchii. Pe muchia de la nodul $x$ la $y$ se găseşte probabilitate $p{~x, y~}$  cu $0 < p_{muchie} &le; 1$.

Se dă un arbore cu $N &ge; 2$ noduri şi probabilităţi $p$ pe muchii. Pe muchia de la nodul $x$ la $y$ se găseşte probabilitatea $p{~x, y~}$  cu $0 < p{~x, y~} &le; 1$.

În fiecare nod se află câte o pisică flămândă. Pe fiecare muchie se alfă câte o plăcintă gustoasă, toată numai şoricei, whiskas, lăptic, etc. Toate plăcintele sunt iniţial acoperite, practic invizibile pisicuţelor.
Plăcintele vor fi dezvelite pe rând şi bine-cunoscutul nostru personaj, Marcel, are onoarea de a stabili ordinea în care plăcintele vor fi arătate pisicuţelor. Atunci când plăcinta de pe muchia de la nodul $x$ la nodul $y$ este dezvelită, se întâmplă una dintre următoarele:

h2. Date de intrare

Fişierul de intrare $pisici.in$ contine, pe prima linie, numarul $n$. Nodurile din arbore sunt numerotate cu numere de la $1$ la $n$. Pe a doua linie se afla $n - 1$ numere, reprezentand sirul $t$ (sa notam cu $t[i]$ al $i$-ulea dintre aceste numere), cu semnificaţia că există muchie între $i + 1$ şi $t[i]$ pentru $i = 1, 2, ... n - 1$. Pe a treia linie se afla $n - 1$ numere, reprezentand sirul $v$, cu semnificaţia că $p{~i+1, t[i]~} = 2^{-v[i]}^$. *Aceste numere sunt numere întregi pentru a evita erorile de precizie*. Se garantează că $0 ≤ v[i] ≤ 10^9^$ si ca $1 ≤ t[i] ≤ i$.

Fişierul de intrare $pisici.in$ contine, pe prima linie, numarul $n$. Nodurile din arbore sunt numerotate cu numere de la $1$ la $n$. Pe a doua linie se afla $n - 1$ numere, reprezentand sirul $t$ (sa notam cu $t[i]$ al $i$-ulea dintre aceste numere), cu semnificaţia că există muchie între $i + 1$ şi $t[i]$ pentru $i = 1, 2, ... n - 1$. Pe a treia linie se afla $n - 1$ numere, reprezentand sirul $v$, cu semnificaţia că $p{~i+1, t[i]~} = 2^-v[i]^$. *Aceste numere sunt numere întregi pentru a evita erorile de precizie*. Se garantează că $0 ≤ v[i] ≤ 10^9^$ si ca $1 ≤ t[i] ≤ i$.

h2. Date de ieşire

În fişierul de ieşire $pisici.out$ se va afla un număr întreg $r$, cu proprietatea ca probabilitatea $q$ cerută în enunţ să satisfacă $q = 2^{-r}^$. Numărul acesta se poate demonstra că este mereu întreg.

În fişierul de ieşire $pisici.out$ se va afla un număr întreg $r$, cu proprietatea ca probabilitatea $q$ cerută în enunţ să satisfacă $q = 2^-r^$. Numărul acesta se poate demonstra că este mereu întreg.

h2. Restricţii

În primul exemplu, ordinea dezvelirii plăcintelor de pe muchie este: (1 3), (1 2), (3 4), (1 5).

În al doilea exemplu, exista o ordine pentru care răspunsul ar fi fost mai mică ca cea din exemplu, numai că aceasta presupunea ca sa fi fost posibil ca două pisici să refuze ambele plăcinta dintre ele (scenariul 3, interzis)!

În al doilea exemplu, exista o ordine pentru care răspunsul ar fi fost mai mic decat cel din exemplu, numai că aceasta presupunea ca sa fi fost posibil ca două pisici să refuze ambele plăcinta dintre ele (scenariul 3, interzis)!

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