==Include(page="template/taskheader" task_id="stramosi")==

==Include(page="template/taskheader" task_id="stramosi")==
 
Familia lui Gigel este foarte numeroasa, avand exact $N$ membri. Fiecare membru stie cine este stramosul lui direct, mai putin cativa membri care sunt foarte batrani si nu mai tin minte nici macar cine a fost stramosul lor direct. Gigel, fiind o fire curioasa a facut un inventar al familiei sale, in sensul ca a numerotat fiecare membru cu un numar distinct intre 1 si $N$ si stie de asemenea pentru fiecare membru, care este stramosul lui direct (daca acesta exista). Curiozitatea lui este si mai mare, in sensul ca isi pune $M$ intrebari de forma: _"Care este al $P$-lea stramos al membrului cu numarul $Q$?"_.
 
h2. Cerinta
 
Scrieti un program care raspunde corect la toate cele M intrebari ale lui Gigel.
 
h2. Date de intrare
 
Pe prima linia a fisierului $stramosi.in$ se afla numerele $N$ si $M$. Pe a doua linie se afla $N$ numere intregi, reprezentand stramosii tuturor membrilor, incepand cu membrul $1$ si terminand cu membrul $N$. Daca un membru nu are stramos, atunci in fisier se va afla numarul $0$. Pe urmatoarele $M$ linii se afla perechi de numere $Q$ si $P$, reprezentand o intrebare de forma: _"Care este al $P$-lea stramos al membrului cu numarul $Q$?"_.
 
h2. Date de iesire
 
Pe fiecare din cele $M$ linii ale fisierului $stramosi.out$ se vor afla raspunsurile la intrebari, adica numerele de ordine al stramosilor (sau $0$ daca identitatea stramosului nu este cunoscuta)
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 250 000$
* $1 ≤ M ≤ 300 000$
* $Numarul de ordine al stramosului oricarui membru este mai mic sau egal cu numarul de ordine al acelui membru$
 
h2. Exemplu
 
table(example). |_. stramosi.in |_. stramosi.out |
|13 7
0 1 2 2 4 1 6 0 8 8 10 10 12
5 2
3 2
7 1
1 3
13 3
9 2
11 1
|2
1
6
0
8
0
10
|
 
 
 
==Include(page="template/taskfooter" task_id="stramosi")==
 
 

==Include(page="template/raw")==
 
Stramosi
 
 
 
Familia lui Gigel este foarte numeroasa, avand exact N membri. Fiecare membru stie cine este stramosul lui direct, mai putin cativa membri care sunt foarte batrani si nu mai tin minte nici macar cine a fost stramosul lor direct.
 
Gigel, fiind o fire curioasa a facut un inventar al familiei sale, in sensul ca a numerotat fiecare membru cu un numar distinct intre 1 si N si stie deasemenea pentru fiecare membru, care este stramosul lui direct (daca acesta exista). Curiozitate lui este si mai mare, in sensul ca isi pune M intrebari de forma: "care este al P-lea stramos al membrului cu numar Q?".
 
h2. Cerinta
 
Scrieti un program care raspunde corect la toate cele M intrebari ale lui Gigel.
 
 
 
Fisier de intrare
 
Pe prima linia a fisierului stramosi.in se afla numerele N si M.
 
Pe a doua linie se afla N numere intregi, reprezentand stramosii tuturor membrilor, incepand cu membrul 1 si terminand cu membrul N. Daca un membru nu are stramos, atunci in fisier se va afla numarul 0.
 
Pe urmatoarele M linii se afla perechi de numere Q si P, reprezentand o intrebare de forma "care este al P-lea stramos al membrului cu numar Q?"
 
 
 
Fisier de iesire
 
Pe fiecare din cele M linii ale fisierului stramosi.out se vor afla raspunsurile la intrebari, adica numerele de ordine al stramosilor (sau 0 daca identitatea stramosului nu este cunoscuta)
 
h2. Restrictii
 
S 1 <= N <= 250.000
 
S 1 <= M <= 300.000
 
h2. Exemplu
 
stramosi.in stramosi.out
13 7 2
 
0 1 2 2 4 1 6 0 8 8 10 10 12 1
 
5 2 6
 
3 2 0
 
7 1 8
 
1 3 0
 
13 3 10
 
9 2
 
11 1
 
 
 
 
==Include(page="template/taskfooter" task_id="stramosi")==

37