CSES - Työntekijät II
  • Time limit: 1.00 s
  • Memory limit: 512 MB

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

Tehtäväsi on käsitellä qq kyselyä muotoa: kuka on työntekijöiden aa ja bb alin yhteinen esimies?

Syöte

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

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

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

Tuloste

Tulosta vastaus jokaiseen kyselyyn.

Rajat

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

Esimerkki

Syöte:

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

Tuloste:

3
1
1