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

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än x esimies k tasoa ylempänä?

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 x ja k: kuka on työntekijän x esimies k tasoa ylempänä?

Tuloste

Tulosta vastaus jokaiseen kyselyyn. Jos kysyttyä esimiestä ei ole, tulosta -1.

Rajat

  • 1 \le n,q \le 2 \cdot 10^5
  • 1 \le e_i \le i-1
  • 1 \le x \le n
  • 1 \le k \le n

Esimerkki

Syöte:

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

Tuloste:

3
1
-1