cinema

Cinema

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

Poveste si cerinta...

Un grup de $N$ prieteni se duc la cinema. Fiecare dintre ei si-a cumparat bilet separat, insa conform intelegerii initiale toti si-au luat bilete in acelasi rand. Ajungand dupa inceputul filmului, ei se aseaza la intamplare pe acel rand. Fiecare dintre cei $N$ prieteni considera ca locul de pe biletul sau este cel mai bun, asa ca fiecare doreste sa ajunga pe locul sau. Pentru a nu deranja prea tare restul spectatorilor ei se hotarasc ca in fiecare minut, mai multe perechi de persoane sa-si schimbe locurile intre ele. La fiecare minut, numarul de schimbari de locuri poate fi oricat de mare, insa o persoana nu poate participa decat la o singura astfel de schimbare. Pentru simplitate, consideram ca persoana $1$ are biletul cu locul $1$, persoana $2$ are biletul cu locul $2$, si asa mai departe, persoana $N$ are biletul cu locul $N$.
 
h2. Cerinta
 
Aflati numarul minim de minute necesare pentru ca fiecare persoana sa ajunga pe locul sau.

h2. Date de intrare

...

Pe prima linie a fisierului $cinema.in$ este scris numarul de prieteni $N$. Pe urmatoarea linie se afla $N$ numere reprezentand locul pe care s-a asezat initial fiecare prieten. Mai exact, a $i$-a valoare reprezinta locul pe care s-a asezat persoana $i$.

h2. Date de iesire

...

Prima linie a fisierului $cinema.out$ va contine numarul minim $M$ de minute necesare pentru ca fiecare persoana sa ajunga pe locul sau. Urmeaza $M$ linii cu urmatoarea structura: numarul $R$ de mutari care sunt executate la minutul respectiv, iar apoi $R$ perechi de numere $i$ $j$, separate printr-un spatiu, avand semnificatia ca in minutul respectiv persoana $i$ isi schimba locul cu persoana $j$.

h2. Restrictii

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

* $2 ≤ N ≤ 1000$
* Evaluarea se face pe $10$ teste. Punctajul primit pentru fiecare test ordonat corect este
$[M ~Ok~ /M ~ultilizator~ * 10]$.

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

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

| 3
3 1 2
| 2
1 1 2
1 2 3

|

h3. Explicatie
 
...
 

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

2201