Fişierul intrare/ieşire:ar.in, ar.outSursăLot Măgurele 2016 - Baraj 6 Seniori
AutorVlad GavrilaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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

Exemplu

ar.inar.outExplicatie
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?