Cinema

cinema

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

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.

Poveste si cerinta...

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.

...

h2. Date de iesire

Prima linie a fisier 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$

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

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

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

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

|
h3. Explicatie