Fişierul intrare/ieşire:stramosi.in, stramosi.outSursăinfo-arena 1.0
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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?".

Cerinta

Scrieti un program care raspunde corect la toate cele M intrebari ale lui Gigel.

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?".

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)

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

Exemplu

stramosi.instramosi.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content