fotbal

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.

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.

Date de intrare

Fişierul fotbal.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.

Date de ieşire

Fişierul fotbal.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.

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

Exemple

fotbal.in

4 2
1 2
3 4

fotbal.out

2
1
3

Explicaţii

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.