stramosi

Stramosi

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

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

Poveste ...

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

...
 
h2. Restrictii
 
...

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

| stramosi.in | stramosi.out |
| linia1
linia2
linia3
| linia1
linia2

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/taskfooter" task_id="stramosi")==
 
 

37