Ca să-şi petreacă timpul într-un mod plăcut, Hetty a decis să deschidă cartea de matematică şi să-şi aleagă o problemă la care să se gândească în timp ce face curăţenie prin casă. În carte a găsit următoarea cerinţă:

Se dă un graf neorientat cu $N$ noduri şi $M$ muchii, care are proprietatea de a fi aproape $R-regulat$, unde $R$ este un număr natural dat. Un graf este aproape $q-regulat$ dacă gradul oricărui nod $x$ (numărul de noduri cu care se învecinează $x$) este fie $q$, fie $q-1$. Se cere să se determine dacă este posibil să se elimine o submulţime de muchii din graful iniţial, astfel încât graful rezultat prin eliminarea acestor muchii să fie aproape $(R-1)$ regulat. În cazul în care acest lucru este posibil, se cere să se determine şi submulţimea de muchii care trebuie eliminate.

Se dă un graf  neorientat cu $N$ noduri şi $M$ muchii, care are proprietatea de a fi aproape $R-regulat$, unde $R$ este un număr natural dat. Un graf este aproape $q-regulat$ dacă gradul oricărui nod $x$ (numărul de noduri cu care se învecinează $x$) este fie $q$, fie $q-1$. Se cere să se determine dacă este posibil să se elimine o submulţime de muchii din graful iniţial, astfel încât graful rezultat prin eliminarea acestor muchii să fie aproape $(R-1)$ regulat. În cazul în care acest lucru este posibil, se cere să se determine şi submulţimea de muchii care trebuie eliminate.

h2. Date de intrare