// Maksymalne skojarzenia
// Data: 26.10.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->data;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

queue Q;                          // Kolejka
int *Color;                       // Tablica kolorów wierzchołków
slistEl **graf;                   // Tablica list sąsiedztwa
int **C;                          // Macierz przepustowości
int **F;                          // Macierz przepływów netto
int *P;                           // Tablica poprzedników
int *CFP;                         // Tablica przepustowości rezydualnych
int n,m,fmax,cp,v,u,i,j;          // Zmienne proste algorytmu
bool esc;                         // Do wychodzenia z zagnieżdżonych pętli
slistEl *pr, *rr;                 // Wskaźniki elementów listy

// Funkcja zwraca true, jeśli graf jest dwudzielny.
// Ustala kolory wierzchołków w tablicy Color
//------------------------------------------------
bool isBipartite()
{
  for(int i = 0; i < n; i++)      // Przechodzimy przez kolejne wierzchołki
    if(!Color[i])                 // Szukamy wierzchołka szarego
    {
      Color[i] = 1;               // Wierzchołek startowy kolorujemy na czerwono
      Q.push(i);                  // i umieszczamy w kolejce

      while(!Q.empty())           // Przejście BFS
      {
        v = Q.front();            // Pobieramy wierzchołek z kolejki
        Q.pop();                  // Pobrany wierzchołek usuwamy z kolejki
        for(pr = graf[v]; pr; pr = pr->next) // Przeglądamy sąsiadów wierzchołka v
        {
          u = pr->data;           // pobieramy z listy sąsiedztwa numer sąsiada
          if(Color[u] == Color[v]) return false;

          if(!Color[u])           // Jeśli wierzchołek nie jest odwiedzony,
          {
            Color[u] = -Color[v]; // kolorujemy go na kolor przeciwny
            Q.push(u);            // i umieszczamy w kolejce
          }
        }
      }
    }

  return true;
}

int main()
{
  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  cin >> n >> m;

  // Tworzymy dane dynamiczne

  Color = new int [n];            // Tablica kolorów wierzchołków
  graf = new slistEl * [n];       // Tablica list sąsiedztwa
  for(i = 0; i < n; i++)
  {
    graf[i] = NULL;
    Color[i] = 0;
  }

  C = new int * [n+2];            // Macierz przepustowości krawędzi
  F = new int * [n+2];            // Macierz przepływów netto
  for(i = 0; i <= n + 1; i++)
  {
    C[i] = new int [n+2];
    F[i] = new int [n+2];
    for(j = 0; j <= n + 1; j++)
    {
      C[i][j] = 0;
      F[i][j] = 0;
    }
  }

  P = new int [n+2];              // Tablica poprzedników
  CFP = new int [n+2];            // Tablica przepustowości rezydualnych

  // Odczytujemy definicje krawędzi i dodajemy je do list sąsiedztwa

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    pr = new slistEl;
    pr->data = u;
    pr->next = graf[v];
    graf[v]  = pr;

    pr = new slistEl;
    pr->data = v;
    pr->next = graf[u];
    graf[u]  = pr;
  }

  if(isBipartite())
  {
    // Ustawiamy macierz przepustowości
    for(i = 0; i < n; i++)
      if(Color[i] == -1)
      {
        for(pr = graf[i]; pr; pr = pr -> next) // Przeglądamy listę sąsiadów wierzchołka niebieskiego
          C[i][pr->data] = 1;     // Przepustowość krawędzi do wierzchołka czerwonego
        C[n][i] = 1;              // Przepustowość krawędzi od źródła
      }
      else C[i][n+1] = 1;         // Przepustowość krawędzi do ujścia

    //**************************************************
    //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
    //**************************************************

    fmax = 0;

    while(true)
    {
      for(i = 0; i <= n + 1; i++) P[i] = -1;

      P[n] = -2;
      CFP[n] = MAXINT;

      while(!Q.empty()) Q.pop();
      Q.push(n);

      esc = false;

      while(!Q.empty())
      {
        v = Q.front(); Q.pop();

        for(u = 0; u <= n + 1; u++)
        {
          cp = C[v][u] - F[v][u];
          if(cp && (P[u] == -1))
          {
            P[u] = v;
            if(CFP[v] > cp) CFP[u] = cp; else CFP[u] = CFP[v];
            if(u == n+1)
            {
              fmax += CFP[n+1];
              i = u;
              while(i != n)
              {
                v = P[i];
                F[v][i] += CFP[n+1];
                F[i][v] -= CFP[n+1];
                i = v;
              }
              esc = true; break;
            }
            Q.push(u);
          }
        }
        if(esc) break;
      }
      if(!esc) break;
    }

    // Wyświetlamy wyniki

    cout << endl
         << "NUMBER OF MATCHES = " << fmax
         << endl;
    if(fmax > 0)
      for(v = 0; v < n; v++)
        for(u = 0; u < n; u++)
          if((C[v][u] == 1) && (F[v][u] == 1))
            cout << v << " - " << u << endl;
  }
  else cout << endl << "NOT A BIBARTITE GRAPH" << endl;

  cout << endl;

  // Usuwamy dane dynamiczne

  delete [] Color;                // Tablica kolorów wierzchołków

  for(i = 0; i < n; i++)
  {
    pr = graf[i];
    while(pr)
    {
      rr = pr;
      pr = pr->next;
      delete rr;
    }
  }

  delete [] graf;                 // Tablica list sąsiedztwa

  for(i = 0; i <= n + 1; i++)
  {
    delete [] C[i];
    delete [] F[i];
  }
  delete [] C;                    // Macierz przepustowości krawędzi
  delete [] F;                    // Macierz przepływów netto

  delete [] P;                    // Tablica poprzedników
  delete [] CFP;                  // Tablica przepustowości rezydualnych

  return 0;
}