rotatii2

Rotatii 2

== include(page="template/taskheader" task_id="rotatii2") ==

Poveste şi cerinţă...

În timp ce făcea curat în Muzeul de Artă Modernă, Henry a găsit o sculptură formată din $N$ bile numerotate cu numere naturale distincte de la $1$ la $N$, ataşate între ele prin $N-1$ bare. Perspicace, Henry a realizat că sculptura reprezintă un arbore binar care are următoarele proprietăţi:
 
# Cu excepţia bilei aflate în vârful sculpturii (care este ataşată de tavan), fiecare bilă $X$ este ataşată printr-o bară de o altă bilă $P$ aflată deasupra ei. Astfel, vom spune că $P$ este părintele lui $X$.
# Fiecare bilă poate avea maxim 2 bile care se ataşează sub ea: opţional una spre stânga (fiul stâng) şi opţional una spre dreapta (fiul drept).
# Dacă o bilă este numerotată cu un număr natural $X$, atunci toate bilele care sunt ataşate de ea, direct sau indirect prin bara dinspre stânga (subarborele stâng) sunt numerotate cu valori mai mici decât $X$, iar toate bilele ataşate de ea, direct sau indirect prin bara dinspre dreapta (subarborele drept) sunt numerotate cu valori mai mari decât $X$.
 
Ca parte a noilor facilităţi interactive ale muzeului, lângă sculptură se află o machetă mobilă a acesteia, formată tot din N bile numerotate de la $1$ la $N$, ataşate între ele prin $N-1$ bare. Deşi bilele ce formează macheta sunt conectate diferit, aceasta respectă aceleaşi reguli (1, 2 şi 3) ca şi sculptura.
 
Deoarece a terminat curăţenia, Henry se gândeşte acum să modifice unele conexiuni din machetă, astfel încât aceasta să aibă aceeaşi formă ca şi sculptura (cu alte cuvinte, pentru fiecare $X$, $1 ≤ X ≤ N$, fiecare bilă numerotată cu $X$ din machetă să fie conectată cu bile având exact aceleaşi numerotări ca ale bilelor conectate cu bila $X$ din sculptură). Ca să facă lucrurile mai interesante, Henry se gândeşte să folosească doar două operaţii pentru a reaşeza macheta:
 
 
# Rotaţia spre dreapta în jurul bilei numerotate cu $D$: pentru două bile $B$ şi $D$, părintele $P$ (care poate exista sau nu) al bilei $D$ şi subarborii $A$, $C$ şi $E$ (care pot exista sau nu) conectaţi ca în figura $1$, se refac legăturile astfel încât $P$, $A$, $B$, $C$, $D$ şi $E$ să fie conectaţi ca în figura $2$.
# Rotaţia spre stânga în jurul bilei numerotate cu $B$: pentru două bile $B$ şi $D$, părintele $P$ (care poate exista sau nu) al bilei $B$ şi subarborii $A$, $C$ şi $E$ (care pot exista sau nu) conectaţi ca în figura $2$, se refac legăturile astfel încât $P$, $A$, $B$, $C$, $D$ şi $E$ să fie conectaţi ca în figura $1$.
 
!problema/rotatii2?IMG1.png!
 
Pentru orice tip de rotaţie, toate celelalte legături între bilele machetei rămân neschimbate. La o privire atentă, se observă că după orice operaţie de rotaţie, macheta respectă în continuare regulile 1, 2 şi 3.
 
Deoarece Henry nu se pricepe cu adevărat decât la curăţenie, vă roagă pe voi să găsiţi o serie de rotaţii care aduc macheta la aceeaşi formă ca şi sculptura.

h2. Date de intrare

Fişierul de intrare $rotatii2.in$ ...

Pe prima linie a fişierului de intrare $rotatii2.in$ se va găsi un număr natural $N$, reprezentând numărul de bile ce compun sculptura. Pe următoarele $N$ linii se va găsi descrierea machetei. Astfel, pentru fiecare $i$, $1 ≤ i ≤ N$, pe linia $1 + i$ se vor găsi câte două numere naturale separate printr-un spaţiu $ML[i]$, $MR[i]$, reprezentând fiul stâng, respectiv fiul drept al bilei etichetate cu $i$ din machetă ( $ML[i]$ şi/sau $MR[i]$ pot fi $0$ în cazul în care bila $i$ nu are fiul corespunzător). În mod similar cu descrierea machetei, pe următoarele $N$ linii se va găsi descrierea sculpturii. Astfel, pentru fiecare $i$, $1 ≤ i ≤ N$, pe linia $1 + N + i$ se vor găsi câte două numere naturale separate printr-un spaţiu $SL[i]$, $SR[i]$, reprezentând fiul stâng, respectiv fiul drept al bilei etichetată cu $i$ din sculptură ( $SL[i]$ şi/sau $SR[i]$ pot fi $0$ în cazul în care bila $i$ nu are fiul corespunzător).

h2. Date de ieşire

În fişierul de ieşire $rotatii2.out$ ...

Pe prima linie a fişierului de ieşire $rotatii2.out$ se va afişa un număr $K$, reprezentând numărul de rotaţii necesare pentru a aduce macheta la aceeaşi formă ca şi sculptura. Pe următoarele $K$ linii se vor afişa, în ordine, operaţiile efectuate, sub forma:
 
* $1 D$, semnificând ca se efectuează o rotaţie spre dreapta în jurul bilei $D$ din machetă (vezi figura);
* $2 B$, semnificând ca se efectuează o rotaţie spre stânga în jurul bilei $B$ din machetă (vezi figura).
 
Între $1$ şi $D$, respectiv $2$ şi $B$ se va afla afişa exact un spaţiu.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1 000 000$
* $K nu trebuie neaparat să fie minim.$
* $Pentru 50% din teste, 1 ≤ N ≤ 2 000$
* $Se vor acorda 70% din punctele pentru un test dacă operaţiile afişate în fişierul de ieşire aduc macheta la forma sculpturii, iar programul rulează în limitele de timp şi memorie indicate, dar K > 2*N.$
* $Se vor acorda 100% din punctele pentru un test dacă, în plus, K ≤ 2*N.$

h2. Exemplu
table(example). |_. rotatii2.in |_. rotatii2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
  0 0
  1 3
  0 0
  2 5
  0 0
  0 0
  1 5
  0 0
  3 0
  4 0
| 2
  1 4
  2 4

|
h3. Explicaţie

...

$Se va efectua întâi o rotaţie spre dreapta în jurul lui 4, apoi o rotaţie spre stânga în jurul lui 4, după cum se poate vedea în figură:$
 
!problema/rotatii1?IMG2.png!

== include(page="template/taskfooter" task_id="rotatii2") ==
 

== include(page="template/taskfooter" task_id="rotatii2") ==