Fişierul intrare/ieşire:	rotatii2.in, rotatii2.out	Sursă	ONI 2014, Baraj
Autor	Vlad Gavrila	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	1.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Rotatii2

Î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:

1. 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.
2. 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).
3. 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:

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

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.

Date de intrare

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

Date de ieşire

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.

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.

Exemplu

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ă:

Cum se trimit solutii?