== include(page="template/taskheader" task_id="fotbal2") ==

Poveste şi cerinţă...

Se apropie sezonul competiţional în Liga I de fotbal din Gheorgheni. Campionatul se desfăşoară după următoarele reguli:
 
* În cazul în care după $90$ de minute de joc scorul este egal, meciul va continua până când una din echipe va înscrie un gol, urmând ca aceasta să fie declarată câştigătoare. În acest fel nu vor exista meciuri terminate la egalitate.
* La finalul unui meci, echipa câştigătoare va primi $1$ punct, iar echipa învinsă va pierde $1$ punct.
Programul competiţiei constă din $M$ meciuri stabilite dinainte de către Federaţia de Fotbal din Gheorgheni. Este posibil ca unele echipe să nu joace deloc aşa cum de asemenea este posibil ca unele echipe să joace împreună de mai multe ori, chiar cu rezultate diferite.
Alexandra este foarte pasionată de fotbal şi ca o microbistă adevărată îşi doreşte un campionat cât mai echilibrat. Astfel ea se întreabă care poate fi diferenţa minimă de punctaj între echipa aflată pe primul loc şi echipa aflată pe ultimul loc în campionat după disputarea celor $M$ meciuri. De asemenea ea ar vrea să stabilească câştigătorul fiecărui meci astfel încât să se obţină această diferenţă minimă de punctaj.
 
h2. Cerinţă
 
Alexandra este o fată foarte ocupată aşa că nu are timp să rezolve astfel de probleme. Totuşi a fost de acord să vă spună vouă câte echipe sunt în campionat, numărul de meciuri care urmează să se dispute precum şi echipele care se vor înfrunta în fiecare meci. Voi trebuie să realizaţi un program care să răspundă întrebărilor Alexandrei.

h2. Date de intrare

Fişierul de intrare $fotbal2.in$ ...

Fişierul de intrare $fotbal2.in$ conţine pe prima linie două numere naturale $N$ şi $M$, separate printr-un spaţiu, reprezentând numărul de echipe din campionat respectiv numărul de meciuri programate. Pe următoarele $M$ linii se vor afla câte două numere $x$ şi $y$, separate printr-un spaţiu, perechea de pe linia $i+1$ din fişier reprezentând echipele care se vor înfrunta în meciul $i$.

h2. Date de ieşire

În fişierul de ieşire $fotbal2.out$ ...

În fişierul de ieşire $fotbal2.out$ va conţine pe prima linie diferenţa minimă de scor între echipa aflată pe primul loc şi echipa aflată pe ultimul loc în clasament.
Următoarele $M$ linii vor conţine câte un număr, numărul de pe linia $i+1$ din fişier reprezentând numărul de ordine al echipei câştigătoare din meciul $i$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 50.000$
* Nu va exista niciun meci în care o echipă să joace cu ea însăşi
* Pentru $5%$ din punctaj $N = 2$
* Pentru $15%$ din punctaj $N, M ≤ 20$
* Pentru $50%$ din punctaj $N, M ≤ 2.000$
* Pentru determinarea diferenţei minime se acordă $20%$ din punctaj

h2. Exemplu
table(example). |_. fotbal2.in |_. fotbal2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2
1 2
3 4
| 2
1
3

|
h3. Explicaţie

...

Primul meci este câştigat de echipa $1$, iar al doilea meci este câştigat de către echipa $3$. La sfârşitul campionatului echipele $1$ si $3$ vor avea câte $1$ punct, iar echipele $2$ si $4$ vor avea $-1$ puncte.
 

== include(page="template/taskfooter" task_id="fotbal2") ==