Ratway-ul conţine şi sediul ghildei tâlharilor din Skyrim. Brynjolf, unul din liderii acesteia, doreşte să dezvolte un nou sistem de capcane pentru a ţine departe gărzile, dar mai întâi reţeaua de tuneluri trebuie să respecte câteva restricţii: tunelurile trebuie sa fie orientate (se pot parcurge într-un singur sens, altfel s-ar activa capcanele), pentru orice intersecţie atât numărul de intrări, cât şi cel de ieşiri trebuie să fie numere pare (prin intrare se înţelege un tunel orientat de la o intersecţie oarecare la intersecţia curentă, iar prin ieşire se înţelege un tunel orientat de la intersecţia curentă la o intersecţie oarecare).

Ajutaţi-l pe Brynjolf să orienteze tunelurile pentru a respecta restricţiile de mai sus. Dacă nu este posibil, construiţi un număr minim de tuneluri, pe care de asemenea să le orientaţi astfel încât reţeaua rezultată să respecte restricţiile.
 

h2. Date de intrare

Prima linie a fişierului $ratway.in$ va conţine două numere naturale $N$ şi $M$, reprezentând numărul de intersecţii şi numărul de tuneluri iniţiale.
Pe fiecare dintre următoarele $M$ linii, se vor găsi două numere naturale, $x$ şi $y$, cu semnificaţia că există tunel între intersecţiile $x$ şi $y$ (intersecţiile sunt reprezentate prin numere naturale de la $1$ la $N$).

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

h2. Date de ieşire

Pe prima linie a fişierului $ratway.out$ afişaţi $K$, numărul minim de tuneluri din reţeaua finală.
Pe fiecare din următoarele $K$ linii afişaţi câte două numere, $x$ şi $y$, semnificând că avem un tunel orientat de la nodul $x$ la nodul $y$. Printre tunelurile afişate, trebuie să se afle şi tunelurile din configuraţia iniţială, unde fiecăruia i-a fost atribuită exact una din cele două direcţii posibile.
Dacă există mai multe soluţii cu $K$ minim, afişaţi pe oricare dintre acestea.

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

h2. Restricţii

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* pentru $15%$ din punctaj $1 ≤ M ≤ 20$ şi nu trebuie construite tuneluri suplimentare
* pentru alte $30%$ din punctaj $1 ≤ N ≤ 1000$, $1 ≤ M ≤ 2000$

* $... ≤ ... ≤ ...$

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

| 3 4
  1 2
  2 3
  1 1
  3 3
| 6
  1 1
  2 1
  2 3
  3 3
  3 1
  1 1

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

|
h3. Explicaţie

Muchiile din fişierul de intrare se orientează
astfel: 1<-2,2- >3,1->1,3- >3.
Se mai adaugă tuneluri orientate: 3->1, 1->1.
Pentru nodul 1 avem: 4 intrări, 2 ieşiri.
Pentru nodul 2 avem: 0 intrări, 2 ieşiri.
Pentru nodul 3 avem: 2 intrări, 2 ieşiri.

 
...

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