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