== include(page="template/taskheader" task_id="ar") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $ar.in$ ...
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$ ...
Î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
* 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.
h2. Exemplu
table(example). |_. ar.in |_. ar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. ar.in |_. ar.out |_. Explicatie |
| 4 5 3
1 2
2 3
3 4
4 1
1 3
| 1
1 3
| 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.
|
== include(page="template/taskfooter" task_id="ar") ==
