== include(page="template/taskheader" task_id="omizi") ==
==Include(page="template/taskheader" task_id="omizi")==
Poveste ...
Intr-un arbore cu $N$ noduri (numerotate de la $1$ la $N$) s-au urcat $M$ omizi (numerotate de la $1$ la $M$). Ca orice fiinta, si omizile noastre faceau politica, si ca orice politician voiau sa ajunga cat mai sus in ierarhia arborelui, spre cat mai multe frunze verzi si gustoase.
Desi are o gandire simpla, totusi fiecare omida tine foarte mult la orientarea sa politica. Astfel omizile de stanga aleg mereu sa mearga in sus si cat mai la stanga, iar cele de dreapta tot mai sus si cat mai spre dreapta. Spre mirarea biologilor, omizile sunt foarte politicoase. Fiecare omida ocupa o singura functie (nod) in arbore si isi asteapta randul spre promovare. Astfel in fiecare zi se efectueaza cate o promovare, si anume a celei mai inalte in functie omizi care poate urca in ierarhie (are un nod fiu vecin neocupat, prin nod fiu vecin omizile intelegand un nod imediat urmator situat mai sus in arbore). Daca sunt mai multe omizi cu acelasi rang, atunci se trage la sorti. Omida zilei alege unde anume vrea sa urce daca are mai multe posibilitati conform orientarii sale politice.
h2. Cerinta
...
Pentru a putea evalua pagubele si pentru a mai salva ceva din calea omizilor politice, gradinarul a hotarat sa apeleze la voi pentru a afla care vor fi pozitile omizilor dupa toate promovarile.
h2. Restrictii
h2. Date de Intrare
...
Pe prima linie a fisierului de intrare $omizi.in$ se gasesc numerele naturale $N$ si $M$, cu semnificatia din enunt. Pe urmatoarele $N$ linii se afla descrierea arborelui. Mai exact, pe linia $i+1$ este scrisa lista fiilor nodului $i$ de la stanga la dreapta ca orientare politica, terminata cu numarul $0$. Fii sunt separati prin cate un spatiu. Pe urmatoarele $M$ linii se gasesc informatii despre omizi. Mai exact, pe linia $N+1+i$ se afla un numar $x$ si o litera majuscula $L$ separate prin spatiu ({$x$} reprezinta numarul nodului in care se afla initial omida $i$, iar $L$ este orientarea politica a omizii $i - S$ pentru stanga si $D$ pentru dreapta).
h2. Date de intrare
h2. Date de Iesire
...
Fisierul de iesire $omizi.out$ va avea $M$ linii, fiecare continand un numar de la $1$ la $N$. Pe linia $i$ este scrisa pozitia finala a omizii $i$ (dupa toate promovarile).
h2. Date de iesire
h2. Restrictii si precizari
...
* $3 ≤ N ≤ 16 000$
* $2 ≤ M ≤ N$
* Radacina arborelui este intotdeauna nodul $1$
* Rangul unei omizi este distanta in numar de muchii de la radacina pana la nodul unde este pozitionata.
* Omizile vor alege intotdeauna nodurile accesibile conform orientarii politice. De exemplu, ordinea preferata pentru o omida ce urmeaza sa fie promovata si care este intr-un nod cu $3$ fii, $4, 5$ si $6$ (de la stanga la dreapta) este $4, 5, 6$ pentru o omida de stanga si $6, 5, 4$ pentru una de dreapta, aceasta alegand primul fiu care nu este deja ocupat
h2. Exemplu
| omizi.in | omizi.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. omizi.in |_. omizi.out |
| 4 2
2 3 0
4 0
0
0
1 S
2 S
| 2
4 |
| 10 5
2 5 9 0
0
8 4 0
0
3 6 7 0
0
10 0
0
0
0
1 D
6 S
7 D
5 S
9 S
| 7
6
10
8
9 |
== include(page="template/taskfooter" task_id="omizi") ==
==Include(page="template/taskfooter" task_id="omizi")==
