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

Fişierul de intrare $ar.in$ conţine pe prima linie numerele naturale $N$, $M$ şi $R$, reprezentând numărul de noduri, numărul de muchii, respectiv faptul că graful dat este $aproape R-regulat$. Pe următoarele $M$ linii se vor afla $M$ perechi de numere $x$ şi $y$, semnificând existenţa unei muchii între nodurile $x$ şi $y$.

Fişierul de intrare ar.in conţine pe prima linie numerele naturale N, M şi R, reprezentând numărul de noduri, numărul de muchii, respectiv faptul că graful dat este aproape R-regulat. Pe următoarele M linii se vor afla M perechi de numere x şi y, semnificând existenţa unei muchii între nodurile x şi y.

h2. Date de ieşire

În fişierul de ieşire $ar.out$ se va afişa, pe prima linie, numărul natural $K$. Acesta are valoarea $-1$ în cazul în care graful iniţial nu poate fi transformat într-unul $aproape (R-1)-regulat$ eliminând o submulţime de muchii. În caz contrar, $K$ reprezintă numărul de muchii eliminate, iar pe următoarele $K$ linii se vor afişa $K$ perechi de numere $x$ şi $y$, fiecare reprezentând faptul că muchia dintre nodurile $x$ şi $y$ din graful iniţial a fost eliminată.

În fişierul de ieşire ar.out se va afişa, pe prima linie, numărul natural K. Acesta are valoarea -1 în cazul în care graful iniţial nu poate fi transformat într-unul aproape (R-1)-regulat eliminând o submulţime de muchii. În caz contrar, K reprezintă numărul de muchii eliminate, iar pe următoarele K linii se vor afişa K perechi de numere x şi y, fiecare reprezentând faptul că muchia dintre nodurile x şi y din graful iniţial a fost eliminată.

h2. Restricţii

* $1 ≤ N ≤ 20 000$
* $1 ≤ M ≤ 200 000$
* $2 ≤ R < N$

* 1 ≤ N ≤ 20 000
* 1 ≤ M ≤ 200 000
* 2 ≤ R < N

* Orice soluţie corectă va fi acceptată, în cazul în care aceasta există.
* Există maxim o muchie între fiecare pereche de noduri.

* Pentru teste în valoare de $20$ puncte, $M ≤ 20$.

* Pentru teste în valoare de 20 puncte, M ≤ 20.

h2. Exemplu