- Time limit: 1.00 s
- Memory limit: 128 MB
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$: henkilöiden määrä ja kyselyiden määrä. Henkilöt on numeroitu $1,2,\ldots,n$. Suvun kantaisä on henkilö 1, ja kaikki muut sukupuussa ovat hänen jälkeläisiään.
Sitten syötteessä on $n-1$ riviä, jotka kuvaavat sukulaisuussuhteet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$. Tämä tarkoittaa, että $a$ on $b$:n vanhempi.
Lopuksi syötteessä on $q$ riviä, joista jokainen kuvaa yhden kyselyn. Kyselyssä on kokonaisluvut $x$ ja $k$: kuka on $k$ tasoa ylempänä henkilöä $x$ sukupuussa?
Tuloste
Tulosta vastaus jokaiseen kyselyyn. Jos kyselyn kuvaamaa henkilöä ei ole olemassa, niin tulosta "QAQ".
Rajat
- $1 \le n,q \le 10^5$
- $1 \le a,b,x \le n$
- $0 \le k \le n-1$
Syöte:
5 3
1 2
1 3
3 4
3 5
4 1
4 2
4 3
Tuloste:
3
1
QAQ