rotatii

Time limit: 0.75s Memory limit: 256MB Input: rotatii.in Output: rotatii.out

În timp ce făcea curat în Muzeul de Artă Modernă, Henry a găsit o sculptură formată din NN bile numerotate cu numere naturale distincte de la 11 la NN, ataşate între ele prin N1N-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ă XX este ataşată printr-o bară de o altă bilă PP aflată deasupra ei. Astfel, vom spune că PP este părintele lui XX.
  2. Fiecare bilă poate avea maxim 22 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 XX, 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 XX, iar toate bilelele ataşate de ea, direct sau indirect prin bara dinspre dreapta (subarborele drept) sunt numerotate cu valori mai mari decât XX.

Ca parte a noilor facilităţi interactive ale muzeului, lângă sculptură se află o machetă mobilă a acesteia, formată tot din NN bile numerotate de la 11 la NN, ataşate între ele prin N1N-1 bare. Deşi bilele ce formează macheta sunt conectate diferit, aceasta respectă aceleaşi reguli (11, 22 și 33) 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 XX, 1XN1 ≤ X ≤ N, fiecare bilă numerotată cu XX din machetă să fie conectată cu bile având exact aceleași numerotări ca ale bilelor conectate cu bila XX 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 DD: pentru două bile BB și DD, părintele PP (care poate exista sau nu) al bilei DD şi subarborii AA, CC și EE (care pot exista sau nu) conectaţi ca în figura 1, se refac legăturile astfel încât P,A,B,C,DP, A, B, C, D şi EE să fie conectaţi ca în figura 2.
  2. Rotaţia spre stânga în jurul bilei numerotate cu BB: pentru două bile BB și DD, părintele PP (care poate exista sau nu) al bilei BB şi subarborii AA, CC și EE (care pot exista sau nu) conectaţi ca în figura 2, se refac legăturile astfel încât P,A,B,C,DP, A, B, C, D şi EE 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 11, 22 şi 33.

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 rotatii.in se va găsi un număr natural NN, reprezentând numărul de bile ce compun sculptura. Pe următoarele NN linii se va găsi descrierea machetei. Astfel, pentru fiecare ii, 1iN1 ≤ i ≤ N, pe linia 1+i1 + i se vor găsi câte două numere naturale separate printr-un spațiu ML[i]ML[i], MR[i]MR[i], reprezentând fiul stâng, respectiv fiul drept al bilei etichetate cu ii din machetă (ML[i]ML[i] și/sau MR[i]MR[i] pot fi 00 în cazul în care bila ii nu are fiul corespunzător). În mod similar cu descrierea machetei, pe următoarele NN linii se va găsi descrierea sculpturii. Astfel, pentru fiecare ii, 1iN1 ≤ i ≤ N, pe linia 1+N+i1 + N + i se vor găsi câte două numere naturale separate printr-un spațiu SL[i],SR[i]SL[i], SR[i], reprezentând fiul stâng, respectiv fiul drept al bilei etichetată cu ii din sculptură (SL[i]SL[i] și/sau SR[i]SR[i] pot fi 00 în cazul în care bila ii nu are fiul corespunzător).

Date de ieșire

Pe prima linie a fișierului de ieșire rotatii.out se va afișa un număr KK, reprezentând numărul de rotații necesare pentru a aduce macheta la aceeași formă ca și sculptura. Pe următoarele KK linii se vor afișa, în ordine, operațiile efectuate, sub forma:

  • 1 D1 \ D, semnificând ca se efectuează o rotație spre dreapta în jurul bilei DD din machetă (vezi figura);
  • 2 B2 \ B, semnificând ca se efectuează o rotație spre stânga în jurul bilei BB din machetă (vezi figura).

Între 11 şi DD, respectiv 22 şi BB se va afla afişa exact un spaţiu.

Restricții și precizări

  • 1N1 000 0001 ≤ N ≤ 1 \ 000 \ 000
  • KK nu trebuie neaparat să fie minim.
  • Pentru 5050% din teste, 1N2 0001 ≤ N ≤ 2 \ 000
  • Se vor acorda 7070% 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>2NK > 2 \cdot N.
  • Se vor acorda 100100% din punctele pentru un test dacă, în plus, K2NK ≤ 2 \cdot N.

Exemplu

rotatii.in

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

rotatii.out

2
1 4
2 4

Explicații

Se va efectua întâi o rotaţie spre dreapta în jurul lui 44, apoi o rotaţie spre stânga în jurul lui 44, după cum se poate vedea în figură

Log in or sign up to be able to send submissions!