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

program maxmatch;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push (v : integer);
      procedure pop;
  end;

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

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push (v : integer);
var
  p : PslistEl;
begin
  new (p);
  p^.next := nil;
  p^.data := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose (p);
  end;
end;

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

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

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

      while not Q.empty do // Przejście BFS
      begin
        v := Q.front;     // Pobieramy wierzchołek z kolejki
        Q.pop;            // Pobrany wierzchołek usuwamy z kolejki
        pr := graf [v]; // Przeglądamy sąsiadów wierzchołka v
        while pr <> nil do
        begin
          u := pr^.data; // pobieramy z listy sąsiedztwa numer sąsiada
          if Color [u] = Color [v] then Exit (false);

          if Color [u] = 0 then  // Jeśli wierzchołek nie jest odwiedzony,
          begin
            Color [u] := -Color [v]; // kolorujemy go na kolor przeciwny
            Q.push (u); // i umieszczamy w kolejce
          end;
          pr := pr^.next; // Następny sąsiad
        end;
      end;
    end;

  isBipartite := true;
end;

begin
  Q.init;                 // Inicjujemy kolejkę

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

  read (n, m);

  // Tworzymy dane dynamiczne

  SetLength (Color, n); // Tablica kolorów wierzchołków
  SetLength (graf, n);  // Tablica list sąsiedztwa
  for i := 0 to n - 1 do
  begin
    graf [i] := nil;
    Color [i] := 0;
  end;

  SetLength (C, n+2); // Macierz przepustowości krawędzi
  SetLength (F, n+2); // Macierz przepływów netto
  for i := 0 to n + 1 do
  begin
    SetLength (C [i], n+2);
    SetLength (F [i], n+2);
    for j := 0 to n + 1 do
    begin
      C [i][j] := 0;
      F [i][j] := 0;
    end;
  end;

  SetLength (P, n+2);   // Tablica poprzedników
  SetLength (CFP, n+2); // Tablica przepustowości rezydualnych

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

  for i := 1 to m do
  begin
    read (v, u);
    new (pr);
    pr^.data := u;
    pr^.next := graf [v];
    graf [v]  := pr;

    new (pr);
    pr^.data := v;
    pr^.next := graf [u];
    graf [u]  := pr;
  end;

  if isBipartite then
  begin
    // Ustawiamy macierz przepustowości
    for i := 0 to n - 1 do
      if Color [i] = -1 then
      begin
        pr := graf [i];       // Przeglądamy listę sąsiadów wierzchołka niebieskiego
        while pr <> nil do
        begin
          C [i][pr^.data] := 1; // Przepustowość krawędzi do wierzchołka czerwonego
          pr := pr^.next;       // Następny sąsiad
        end;
        C [n][i] := 1;      // Przepustowość krawędzi od źródła
      end
      else C [i][n+1] := 1; // Przepustowość krawędzi do ujścia

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

    fmax := 0;

    while true do
    begin
      for i := 0 to n + 1 do P [i] := -1;

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

      while not Q.empty do Q.pop;
      Q.push (n);

      esc := false;

      while not Q.empty do
      begin
        v := Q.front; Q.pop;

        for u := 0 to n + 1 do
        begin
          cp := C [v][u] - F [v][u];
          if(cp <> 0) and (P [u] = -1) then
          begin
            P [u] := v;
            if CFP [v] > cp then CFP [u] := cp else CFP [u] := CFP [v];
            if u = n + 1 then
            begin
              inc (fmax, CFP [n+1]);
              i := u;
              while i <> n do
              begin
                v := P [i];
                inc (F [v][i], CFP [n+1]);
                dec (F [i][v], CFP [n+1]);
                i := v;
              end;
              esc := true; break;
            end;
            Q.push (u);
          end;
        end;
        if esc then break;
      end;
      if not esc then break;
    end;

    // Wyświetlamy wyniki

    writeln;
    writeln('NUMBER OF MATCHES = ', fmax);
    writeln;
    if fmax > 0 then
      for v := 0 to n - 1 do
        for u := 0 to n - 1 do
          if(C [v][u] = 1) and (F [v][u] = 1) then
            writeln(v, ' - ', u);
  end
  else
  begin
    writeln;
    writeln('NOT A BIBARTITE GRAPH');
  end;

  writeln;

  // Usuwamy dane dynamiczne

  SetLength (Color, 0); // Tablica kolorów wierzchołków

  for i := 0 to n - 1 do
  begin
    pr := graf [i];
    while pr <> nil do
    begin
      rr := pr;
      pr := pr^.next;
      dispose (rr);
    end;
  end;

  SetLength (graf, 0); // Tablica list sąsiedztwa

  for i := 0 to n + 1 do
  begin
    SetLength (C [i], 0);
    SetLength (F [i], 0);
  end;
  SetLength (C, 0);   // Macierz przepustowości krawędzi
  SetLength (F, 0);   // Macierz przepływów netto

  SetLength (P, 0);   // Tablica poprzedników
  SetLength (CFP, 0); // Tablica przepustowości rezydualnych
end.

// 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;}

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

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  Data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push (ByVal x As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->Data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim Shared As queue Q              ' Kolejka
Dim Shared As Integer Ptr VColor, P, CFP ' Tablice kolorów, poprzedników i przepustowości rezydualnych
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim As Integer Ptr Ptr C, F        ' Macierze przepustowości i przepływów netto
Dim Shared As Integer n, m, fmax, cp, v, u, i, j ' Zmienne proste algorytmu
Dim As Byte esc                    ' Do wychodzenia z zagnieżdżonych pętli
Dim Shared As slistEl Ptr pr, rr   ' Wskaźniki elementów listy

' Funkcja zwraca true, jeśli graf jest dwudzielny.
' Ustala kolory wierzchołków w tablicy Color
'------------------------------------------------
Function isBipartite() As Byte

  For i = 0 To n - 1      ' Przechodzimy przez kolejne wierzchołki
    If VColor [i] = 0 Then ' Szukamy wierzchołka szarego
      VColor [i] = 1    ' Wierzchołek startowy kolorujemy na czerwono
      Q.push (i)        ' i umieszczamy w kolejce

      While Q.empty() = 0 ' Przejście BFS
        v = Q.front()    ' Pobieramy wierzchołek z kolejki
        Q.pop()          ' Pobrany wierzchołek usuwamy z kolejki
        pr = graf [v]
        While pr <> 0     ' Przeglądamy sąsiadów wierzchołka v
          u = pr->Data    ' pobieramy z listy sąsiedztwa numer sąsiada
          If VColor [u] = VColor [v] Then return 0

          If VColor [u] = 0 Then ' Jeśli wierzchołek nie jest odwiedzony,
            VColor [u] = -VColor [v] ' kolorujemy go na kolor przeciwny
            Q.push (u)  ' i umieszczamy w kolejce
          End If
          pr = pr -> Next
        Wend
      Wend
    End If
  Next
  return 1
End Function

Open Cons For Input As #1

' Ze standardowego wejścia odczytujemy
' n - liczbę wierzchołków w grafie sieci
' m - liczbę krawędzi

Input #1, n, m

' Tworzymy dane dynamiczne

VColor = New Integer [n]   ' Tablica kolorów wierzchołków
graf = New slistEl Ptr [n] ' Tablica list sąsiedztwa
For i = 0 To n - 1
  graf [i] = 0
  VColor [i] = 0
Next

C = New integer Ptr [n + 2] ' Macierz przepustowości krawędzi
F = New Integer Ptr [n + 2] ' Macierz przepływów netto
For i = 0 To n = 1
  C [i] = New Integer [n + 2]
  F [i] = New Integer [n + 2]
  For j = 0 To n = 1
    C [i][j] = 0
    F [i][j] = 0
  Next
Next

P = New Integer [n + 2]   ' Tablica poprzedników
CFP = New Integer [n + 2] ' Tablica przepustowości rezydualnych

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

For i = 1 To m
  Input #1, 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
Next

If isBipartite() = 1 Then
  ' Ustawiamy macierz przepustowości
  For i = 0 To n - 1
    If VColor [i] = -1 Then
      pr = graf [i]
      While pr <> 0      ' Przeglądamy listę sąsiadów wierzchołka niebieskiego
        C [i][pr->data] = 1  ' Przepustowość krawędzi do wierzchołka czerwonego
        pr = pr -> Next
      Wend 
      C [n][i] = 1   ' Przepustowość krawędzi od źródła
    Else
      C [i][n+1] = 1 ' Przepustowość krawędzi do ujścia
    End If
  Next

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

  fmax = 0

  While 1
    For i = 0 To n + 1
    	P [i] = -1
    Next

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

    While Q.empty() = 0
    	Q.pop()
    Wend
    Q.push (n)

    esc = 0

    While Q.empty() = 0
      v = Q.front()
      Q.pop()

      For u = 0 To n + 1
        cp = C [v][u] - F [v][u]
        if(cp > 0) AndAlso (P [u] = -1) Then
          P [u] = v
          If CFP [v] > cp Then
          	CFP [u] = cp
          Else
          	CFP [u] = CFP [v]
          EndIf
          If u = n+1 Then
            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
            Wend
            esc = 1
            Exit For
          End If
          Q.push (u)
        End If
      Next
      If esc = 1 Then Exit While
    Wend 
    If esc = 0 Then Exit While
  Wend

  ' Wyświetlamy wyniki

  Print
  Print "NUMBER OF MATCHES =";fmax
  Print
  If fmax > 0 Then
    For v = 0 To n - 1
      For u = 0 To n - 1
        if(C [v][u] = 1) AndAlso (F [v][u] = 1) Then
          Print Using "& - &";v;u
        End If
      Next
    Next
  End If
Else
  Print
  Print "NOT A BIBARTITE GRAPH"
End If
Print

' Usuwamy dane dynamiczne

Delete [] VColor ' Tablica kolorów wierzchołków

For i = 0 To n - 1
  pr = graf [i]
  While pr <> 0
    rr = pr
    pr = pr->Next
    Delete rr
  Wend
Next

Delete [] graf ' Tablica list sąsiedztwa

For i = 0 To n + 1
  Delete [] C [i]
  Delete [] F [i]
Next
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

End