== include(page="template/taskheader" task_id="telefon2") ==
Poveste şi cerinţă...
Cei $N$ elevi 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 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.
h2. Cerinta
Determinaţi o succesiune cu număr minim de modificări, în urmă cărora telefonul fără fir să funcţioneze corect.
h2. Date de intrare
Fişierul de intrare $telefon2.in$ ...
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 ≤ i ≤ N)$.
h2. Date de ieşire
În fişierul de ieşire $telefon2.out$ ...
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$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 < N ≤ 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, nculsiv el însuşi.
* Pentru alte $20%$ din teste $N ≤ 1000$
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
h2. Exemplu
table(example). |_. telefon2.in |_. telefon2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10
6 9 2 7 3 1 9 3 7 9
| 5
2 4
6 10
8 5
9 1
10 8
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="telefon2") ==
