| Fişierul intrare/ieşire: | autostrazi2.in, autostrazi2.out | Sursă | Infoarena Monthly 2012, Runda 12 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Mihai-Alexandru Dusmanu •dushmi |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Autostrazi2
Presedintele, observand nemultumirea soferilor referitoare la situatia soselelor din Romania, s-a hotarat sa transforme cateva din strazile existente in autostrazi. Fiind date: N - numarul de orase, M - numarul de strazi si care sunt acestea, sa se determine un set de N / 2 strazi care sa fie transformate in autostrazi astfel incat fiecare oras sa aiba exact o autostrada adiacenta. La momentul actual, exista multe strazi in Romania, din fiecare oras plecand cel putin N / 2.
Date de intrare
Fişierul de intrare autostrazi2.in va contine pe prima linie N, numarul de orase, si M, numarul de strazi nereparate. Pe urmatoarele M linii se vor afla cate 2 numere reprezentand extremetitatile strazilor.
Date de ieşire
În fişierul de ieşire autostrazi2.out se vor afla N / 2 linii, fiecare continand extremitatile unei strazi care va fi transformata in autostrada.
Restricţii
- 1 ≤ N ≤ 1000, N par
- 1 ≤ M ≤ 500000
- Se garanteaza ca intre oricare doua noduri exista cel mult o muchie.
- Se garanteaza ca intre oricare doua noduri exista cel putin un drum.
- Se garanteaza ca exista solutie. Orice solutie va fi considerata corecta.
Exemplu
| autostrazi2.in | autostrazi2.out |
|---|---|
| 6 9 1 5 1 3 1 6 2 3 2 4 2 5 3 6 4 5 4 6 | 5 4 2 3 1 6 |
