29879번 - MAX-elemendid 다국어

Jukul on $N$ tipuga kahendpuu, mis ei pruugi olla tasakaalus. Puu tipud on nummerdatud $1 \ldots N$ ja puu juur on tipp number $1$. Puu igasse lehte on kirjutatud üks arv. Juku saab igasse ülejäänud tippu paigutada omal valikul kas MIN- või MAX-elemendi. MIN-element kirjutab oma tipu väärtuseks selle alluvate väärtustest väiksema, MAX-element suurema. Juku tahab erinevate arvude kohta teada, mitu MAX-elementi on minimaalselt vaja selleks, et juurtipu väärtuseks kirjutataks antud arvuga võrdne või sellest suurem arv. Kirjuta programm, mis aitab Juku küsimustele vastata.

Sisendi esimesel real on puu tippude arv $N$ ($3 \le N \le 10^5$). Järgmisel $N-1$ real on igaühel kaks täisarvu $A_i$ ja $B_i$ ($1 \le A_i, B_i \le N$, $A_i \ne B_i$), mis tähendab et tippude $A_i$ ja $B_i$ vahel on serv.

Järgnevatel ridadel on igaühel kaks täisarvu $X_j$ ja $Y_j$ ($1 \le X_j \le N$, $0 \le Y_j \le 10^7$), kus $X_j$ on ühe lehttipu indeks ja $Y_j$ sinna kirjutatud väärtus. Selliseid ridu on samapalju kui puus lehti.

Järgmisel real on Juku küsimuste arv $Q$ ($1 \le Q \le 5 \cdot 10^5$). Järgmisel $Q$ real on igaühel üks täisarv $M_k$ ($0 \le M_k \le 10^7$), mille kohta Juku tahab teada minimaalset vajalikku MAX-elementide arvu.

Juku iga küsimuse kohta väljastada üks rida. Kui Juku antud $M_k$ või sellest suurema arvu saamine puu juurtippu on võimalik, väljastada minimaalne selleks vajalike MAX-elementide arv. Kui nii suurt arvu pole võimalik juurtippu saada, siis väljastada vastuseks $-1$. Vastused väljastada küsimuste sisendis olemise järjekorras.