telefon

Cei $N$ elevi ai unei clase s-au hotărât să formeze un „telefon fără fir”. Pentru aceasta, elevii au fost numerotaţi de la $1$ la $N$, apoi fiecare elev şi-a ales un singur coleg (îl vom numi vecin), singurul căruia el îi va putea transmite în mod direct mesajele primite. Telefonul fără fir funcţionează astfel:

• iniţial un elev transmite un mesaj (evident, numai vecinului său);
• fiecare elev care a primit (direct sau indirect) mesajul, transmite mesajul primit mai departe, vecinului său.

Telefonul fără fir funcţionează corect, dacă oricare elev ar iniţia transmiterea mesajului, acesta va ajunge la fiecare dintre cei $N$ elevi (deci inclusiv înapoi la elevul care a iniţiat transmiterea mesajului). Elevii au observat că telefonul lor fără fir nu funcţionează corect. Pentru ca telefonul fără fir să funcţioneze corect, ei se gândesc să realizeze o succesiune de modificări. Printr-o modificare un elev îşi poate schimba vecinul ales.

Cerinţă

Determinaţi o succesiune cu număr minim de modificări, în urmă cărora telefonul fără fir să funcţioneze corect.

Date de intrare

Prima linie a fişierului de intrare telefon.in conţine numărul natural $N$, reprezentând numărul elevilor. Pe cea de a doua linie se află $N$ numere naturale, separate prin câte un spaţiu; al $i$-lea număr reprezintă vecinul ales de copilul $i \ (1 \leq i \leq N)$.

Date de ieșire

Pe prima linie a fişierului de ieşire telefon.out se va scrie un număr natural $k$, reprezentând numărul minim de modificări necesare pentru ca telefonul fără fir să funcţioneze corect. Pe următoarele $k$ linii se va scrie succesiunea modificărilor efectuate, câte o modificare pe o linie. O modificare este specificată prin două numere naturale separate prin spaţiu, $c \ v$, cu semnificaţia că elevul $c$ îşi schimbă vecinul, noul său vecin fiind $v$.

Restricții și precizări

• $1 < N \leq 100 \ 000$
• Dacă există mai multe soluţii, puteţi afişa oricare dintre acestea.
• Pentru $30\%$ din teste se garantează că fiecare elev va fi ales ca vecin de către alt elev
• Pentru alte $30\%$ din teste există cel puţin un elev care va primi direct sau indirect mesajul transmis de către oricare elev, inclusiv el însuşi.
• Pentru alte $20\%$ din teste $N \leq 1 \ 000$
• Se vor acorda punctaje parţiale astfel:
  • $30\%$ din punctajul pe fiecare test, reprezintă numărul minim de modificări
  • Restul de $70\%$ pentru reconstituirea soluţiei

Exemplul 1

telefon.in

10
6 9 2 7 3 1 9 3 7 9

telefon.out

5
2 4
6 10
8 5
9 1
10 8