autostrazi2

Autostrazi2

== include(page="template/taskheader" task_id="autostrazi2") ==

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $autostrazi2.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $autostrazi2.out$ ...

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

h2. Restricţii

* $1 ≤ N ≤ 1000$

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

h2. Exemplu
table(example). |_. autostrazi2.in |_. autostrazi2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="autostrazi2") ==