Fişierul intrare/ieşire:	cinema.in, cinema.out	Sursă	Lista lui Francu
Autor	Cristian Cadar	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

Cerinta

Aflati numarul minim de minute necesare pentru ca fiecare persoana sa ajunga pe locul sau.

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.

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.

Restrictii

• 2 ≤ N ≤ 1000
• Evaluarea se face pe 10 teste. Punctajul primit pentru fiecare test care ordoneaza corect este
  [(M~Ok~ / M~ultilizator~)²]

Exemplu

Cum se trimit solutii?