Code Submission Evaluation System Login

Datatähti-valmennus

Esi-isät


Task | Statistics


CSES - Esi-isät

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 kahden henkilön alin yhteinen esi-isä 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 $a$ ja $b$: kuka on $a$:n ja $b$:n alin yhteinen esi-isä?

Tuloste

Tulosta vastaus jokaiseen kyselyyn.

Rajat
Esimerkki

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


Tuloste:
1
3
1