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