Passaporti

Nella Terra della Concordia ci sono N stati.
Ogni stato confina con qualche altro stato e ogni coppia di stati confinanti è collegata direttamente da un’unica strada.
Se un abitante di uno stato passa in un altro stato adiacente il suo passaporto deve essere controllato una e una sola volta, o al momento dell’entrata nello stato verso cui l’abitante si dirige o all’uscita dello stato da cui parte.

Vi sono M strade e ognuna deve avere esattamente una stazione di controllo passaporti.
La stazione deve essere posizionata all’uscita di uno stato o all’entrata dell’altro.
Dato che le stazioni di controllo passaporti sono molto costose, si vuole fare in modo che tutti gli stati sostengano più o meno lo stesso onere finanziario.
In altre parole, per ogni strada è necessario stabilire in quale stato porre la stazione di controllo.

Si vuole minimizzare la differenza tra il numero di stazioni dello stato che ne ha di più e il numero di stazioni dello stato che ne ha di meno.

Si può fornire una soluzione subottimale.

Dati in Input

Il file input.txt contiene sulla prima riga 2 interi N ed M.
Su ognuna delle successive M righe è contenuta una coppia di interi i e j ad indicare che tra lo stato i e lo stato j esiste una strada.

Dati in Output

Il file output.txt contiene sulla prima riga un intero: la differenza tra il numero di stazioni di controllo passaporto dello stato che ne posside di più e quello che ne possiede di meno.
Ognuna delle successive M righe contiene una coppia di interi i e j a indicare che nella strada che collega gli stati i e j la stazione deve essere posizionata nello stato j.

Assunzioni

• 1 < N ≤ 250
• 1 < M ≤ 10000
• Il tempo di esecuzione massimo è fissato in 2 secondi
• Su un input che ammette differenza minima Q, un output privo di errori viene valutato 1 se la differenza che propone è uguale a Q,1/3 se la differenza che propone è uguale a Q+1, 0 in tutti gli altri casi.

Esempi