MAX-elemendid

문제

Jukul on $NN$ tipuga kahendpuu, mis ei pruugi olla tasakaalus. Puu tipud on nummerdatud $1\dots N1\; \backslash ldots\; N$ ja puu juur on tipp number $11$. 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 $NN$ ($3\le N\le {10}^{5}3\; \backslash le\; N\; \backslash le\; 10^5$). Järgmisel $N-1N-1$ real on igaühel kaks täisarvu $A_{i}A\_i$ ja $B_{i}B\_i$ ($1\le A_i,B_i\le N1\; \backslash le\; A\_i,\; B\_i\; \backslash le\; N$, $A_i\mathrm{\ne }{B}_{i}A\_i\; \backslash ne\; B\_i$), mis tähendab et tippude $A_{i}A\_i$ ja $B_{i}B\_i$ vahel on serv.

Järgnevatel ridadel on igaühel kaks täisarvu $X_{j}X\_j$ ja $Y_{j}Y\_j$ ($1\le X_j\le N1\; \backslash le\; X\_j\; \backslash le\; N$, $0\le Y_j\le {10}^{7}0\; \backslash le\; Y\_j\; \backslash le\; 10^7$), kus $X_{j}X\_j$ on ühe lehttipu indeks ja $Y_{j}Y\_j$ sinna kirjutatud väärtus. Selliseid ridu on samapalju kui puus lehti.

Järgmisel real on Juku küsimuste arv $QQ$ ($1\le Q\le 5\cdot {10}^{5}1\; \backslash le\; Q\; \backslash le\; 5\; \backslash cdot\; 10^5$). Järgmisel $QQ$ real on igaühel üks täisarv $M_{k}M\_k$ ($0\le M_k\le {10}^{7}0\; \backslash le\; M\_k\; \backslash 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}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-1$. Vastused väljastada küsimuste sisendis olemise järjekorras.