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

• $1 \le n,q \le 10^5$
  
• $1 \le a,b \le n$
  

Esimerkki

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

Tuloste:
1
3
1