# 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/rotatii1?IMG1.png!

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

h2. Date de intrare

Pe prima linie a fişierului de intrare $rotatii1.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).

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

Pe prima linie a fişierului de ieşire $rotatii1.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:

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

h2. Exemplu

table(example). |_. rotatii1.in |_. rotatii1.out |

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

| 5
  0 0
  1 3