Fişierul intrare/ieşire:bridges.in, bridges.outSursăConcurs Shumen juniori 2017
AutorAutor NecunoscutAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Missing Bridges

În figura 1 avem 4 insule, reprezentate prin puncte etichetate de la 1 la 4 şi 7 poduri reprezentate prin linii, fiecare dintre ele conectând două puncte diferite. Fiecare pod poate fi traversat în ambele direcţii. Cerinţa este să pornim dintr-o insulă, să parcurgem fiecare pod exact o dată şi să ne reîntoarcem în punctul de plecare. Vom denumi asta: "all-bridges-walk". Acest lucru, în figura 1, este imposibil. Dar este posibil dacă vom construi noi poduri, de exemplu construim podul care conectează insula 4 cu insula 1 şi podul care conectează insula 2 cu insula 3. În figura 2, regiunea are 4 insule şi trei poduri. Dacă se cere "all-bridges-walk" în acest caz, sunt necesare de exemplu două poduri între 3 şi 4. Se dă o ţară cu N insule şi M poduri. Scrieţi un program care să determine numărul minim de poduri ce trebuie construite pentru a obţine un "all-bridges-walk" în ţară.

Date de intrare

Fişierul de intrare bridges.in va conţine pe prima linie un număr N şi un număr M. Pe următoarele M linii se găsesc câte două numere reprezentănd extremităţile fiecărui pod.

Date de ieşire

În fişierul de ieşire bridges.out se va scrie numărul minim necesar de poduri construite, K. Fiecare dintre următoarele K linii conţine extremităţile fiecărui pod construit. Este acceptată orice soluţie corectă. Dacă nu este necesară construcţia vreunui pod se va scrie 0.

Restricţii

  • N ≤ 1 000
  • M ≤ 10 000

Exemplu

bridges.inbridges.out
4 7
1 2
2 3
3 2
2 1
1 4
2 4
3 4
2
1 4
2 3
4 5
1 2
2 3
3 1
3 4
3 4
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici