CSES - 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 nn ja qq: henkilöiden määrä ja kyselyiden määrä. Henkilöt on numeroitu 1,2,,n1,2,\ldots,n. Suvun kantaisä on henkilö 1, ja kaikki muut sukupuussa ovat hänen jälkeläisiään.

Sitten syötteessä on n1n-1 riviä, jotka kuvaavat sukulaisuussuhteet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb. Tämä tarkoittaa, että aa on bb:n vanhempi.

Lopuksi syötteessä on qq riviä, joista jokainen kuvaa yhden kyselyn. Kyselyssä on kokonaisluvut xx ja kk: kuka on kk tasoa ylempänä henkilöä xx sukupuussa?

Tuloste

Tulosta vastaus jokaiseen kyselyyn. Jos kyselyn kuvaamaa henkilöä ei ole olemassa, niin tulosta "QAQ".

Rajat

  • 1n,q1051 \le n,q \le 10^5
  • 1a,b,xn1 \le a,b,x \le n
  • 0kn10 \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