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