Fişierul intrare/ieşire:	zeul.in, zeul.out	Sursă	FMI No Stress 6
Autor	Mihai Nitu	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	0.25 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Por Costel, Zeul

Por Costel a devenit un zeu Xel'Naga puternic dupa ce şi-a combinat esenţa cu străvechiul Ouros. Acum el îi vegheaza pe muritori, fiind o entitate omniscientă şi, la cât de gras e, omniprezentă.

Oamenii trăiesc o viaţă relativ paşnică, făcând fapte bune unul altuia. Por Costel poate să vadă în vidul infinit toate perechile de muritori (x,y) cu proprietatea că muritorul x a dăruit un cocean muritorului y. Por Costel, fiind un zeu benevol, vrea să aducă echilibru lumii făcând în aşa fel încât fiecare muritor a dăruit coceni de tot atâtea ori cât a primit coceni. În această privinţă, el poate manipula un muritor să ofere un cocean altuia. Însă, ca orice zeu, Por Costel vrea să-şi minimizeze numărul de intervenţii în vieţile muritorilor. Por Costel ştie deja soluţia optimă, că doar e omniscient. Voi o puteţi găsi?

Date de intrare

Fişierul de intrare zeul.in va conţine pe prima linie două numere naturale: numărul de muritori N si numărul de daruri de coceni care s-au produs, M. Pe următoarele M linii, se găsesc câte două numere pe linie, x si y, având semnificaţia că muritorul x a oferit un cocean muritorului y.

Date de ieşire

În fişierul de ieşire zeul.out se va găsi pe prima linie numărul minim S de manipulări pe care le-a făcut Por Costel pentru a duce echilibru in lume. Vor urma S linii care vor conţine 2 numere naturale fiecare, semnificând că Por Costel l-a influenţat pe muritorul x să ofere un cocean muritorului y.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 300.000
• Pentru 40% din teste, N ≤ 10.000
• Por Costel must survive

Exemplu

Cum se trimit solutii?