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 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 ≤ i ≤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
• 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, inculsiv 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