- 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