ar

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.

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$.

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ă.

Restricții și precizări

• $1 \leq N \leq 20 \ 000$
• $1 \leq M \leq 200 \ 000$
• $2 \leq 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 \leq 20$.

Exemplu

ar.in

4 5 3
1 2
2 3
3 4
4 1
1 3

ar.out

1
1 3

Explicație

Graful dat este aproape $3$-regulat: nodurile $1$ şi $3$ au $3$ vecini fiecare, în timp ce nodurile $2$ şi $4$ au $2$ vecini fiecare.
Prin eliminarea muchiei $(1, 3)$, toate nodurile au exact $2$ vecini, iar graful devine aproape $2$-regulat.
O altă soluţie posibilă este:
$2$
$1 \ 2$
$3 \ 4$
Astfel, nodurile $2$ şi $4$ rămân cu $1$ vecin fiecare, iar nodurile $1$ şi $3$ rămân cu $2$ vecini fiecare. Şi în acest caz, graful devine aproape $2$-regulat.