Sukupuu

• Time limit: 1.00 s
• Memory limit: 128 MB

Sinulle on annettu kuvaus Uolevin suvun sukupuusta sekä joukko kyselyjä puuta koskien. Jokaisessa kyselyssä sinun tulee ilmoittaa, kuka on tiettyä henkilöä tietyn verran korkeammalla puussa.

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$
  

Esimerkki

Syöte:
5 3
1 2
1 3
3 4
3 5
4 1
4 2
4 3

Tuloste:
3
1
QAQ