Yrityksessä on n työntekijää, joista muodostuu puumainen rakenne, jossa jokaisella työntekijällä on esimies yrityksen johtajaa lukuun ottamatta.

Tehtäväsi on käsitellä q kyselyä muotoa: kuka on työntekijöiden a ja b alin yhteinen esimies?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: työntekijöiden määrä ja kyselyiden määrä. Työntekijät on numeroitu 1,2,\dots,n ja työntekijä 1 on yrityksen johtaja.

Seuraavalla rivillä on n-1 kokonaislukua e_2,\dots,e_n: jokaiselle työntekijälle 2,3,\dots,n hänen esimiehensä.

Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua a ja b: kuka on työntekijöiden a ja b alin yhteinen esimies?

Tuloste

Tulosta vastaus jokaiseen kyselyyn.

Rajat

• 1 \le n,q \le 2 \cdot 10^5
• 1 \le e_i \le i-1
• 1 \le a,b \le n

Esimerkki

Syöte:

5 3
1 1 3 3
4 5
2 5
1 4

Tuloste:

3
1
1