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).

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 Iesire

h2. Restrictii si precizari
* $3 ≤ N ≤ 16 000$

* 2 ≤ M ≤ N

* $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

  9 |
==Include(page="template/taskfooter" task_id="omizi")==

1054