Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | stramosi.in, stramosi.out | Sursă | info-arena 1.0 |
| Autor | Mircea Bogdan Pasoi | Adăugată de | |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Stramosi
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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?".
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)
Restrictii
S 1 <= N <= 250.000
S 1 <= M <= 300.000
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
