Fişierul intrare/ieşire:zeul.in, zeul.outSursăFMI No Stress 6
AutorMihai NituAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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

zeul.inzeul.out
4 4
1 2
1 3
2 4
3 4
2
4 1
4 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?