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 vroiau 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 inteleg 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.
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.
Date
de intrare
Pe prima linie a fisierului
de intrare omizi.in se gasesc
numere naturale N si M.
Pe urmatoarele N linii se afl
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).
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).
Restrictii si precizari
Arborele are mereu
drept radacina nodul 1, iar rangul unei omizi este distanta in numar de muchii
de la radacina pana la nodul unde este pozitionata.
De exemplu ordinea preferata pentru o omida ce urmeaza sa fie promovata si care
este intr-un nod cu 3 fii : 4, 5, 6 (de la stanga la dreapta) este 4, 5, 6 pentru
una de stanga si 6, 5, 4 pentru una de dreapta, aceasta alegand primul fiu neocupat.
3<=N<=16 000
0<=M<=N
Exemple
omizi.in
omizi.out
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
Student Emilian Miron
Universitatea Bucuresti, Facultatea de Matematica si Informatica
Contact: emilian.miron@gmail.com