autostrazi2

Autostrazi2

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

Presedintele, observand nemultumirea soferilor referitoare la situatia soselelor din Romania, s-a hotarat sa transforme cateva din strazile existente in autostrazi. Fiind dat $N$, numarul de orase

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

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

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

| 6 8

| 6 9
  1 5

  1 3
  1 6
  2 3