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

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 pleaca cel putin $N / 2$ - dar toate sunt in stare proasta.

h2. Date de intrare

* $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 9
  1 5

| 6 8

  1 3
  1 6
  2 3