- 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 ja : henkilöiden määrä ja kyselyiden määrä. Henkilöt on numeroitu . Suvun kantaisä on henkilö 1, ja kaikki muut sukupuussa ovat hänen jälkeläisiään.
Sitten syötteessä on riviä, jotka kuvaavat sukulaisuussuhteet. Jokaisella rivillä on kaksi kokonaislukua ja . Tämä tarkoittaa, että on :n vanhempi.
Lopuksi syötteessä on riviä, joista jokainen kuvaa yhden kyselyn. Kyselyssä on kokonaisluvut ja : kuka on :n ja :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