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

program maxmatch;

// Definicja typu
// elementów listy
//----------------
type
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    Data: integer;
  end;

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

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

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

// Konstruktor
//------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

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

// Funkcja zwraca true,
// jeśli graf jest dwudzielny.
// Ustala kolory wierzchołków
// w tablicy Color
//----------------------------
function isBipartite : boolean;
begin
  // Przechodzimy przez
  // kolejne wierzchołki
  for i := 0 to n-1 do
    // Szukamy wierzchołka
    // szarego
    if Color[i] = 0 then
    begin
      // Wierzchołek startowy
      // kolorujemy na czerwono
      Color[i] := 1;
      // i umieszczamy w kolejce
      Q.push(i);
      // Przejście BFS
      while not Q.empty do
      begin
        // Pobieramy wierzchołek
        // z kolejki
        v := Q.front;
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop;
        // Przeglądamy sąsiadów
        // wierzchołka v
        pr := graf [v];
        while pr <> nil do
        begin
          // pobieramy z listy
          // sąsiedztwa numer sąsiada
          u := pr^.data;
          if Color[u] = Color[v] then
            Exit(false);
          // Jeśli wierzchołek
          // nie jest odwiedzony,
          if Color[u] = 0 then
          begin
            // kolorujemy go
            // na kolor przeciwny
            Color[u] := -Color[v];
            // i umieszczamy w kolejce
            Q.push(u);
          end;
          // Następny sąsiad
          pr := pr^.next;
        end;
      end;
    end;
  isBipartite := true;
end;

begin
  // Inicjujemy kolejkę
  Q.init;
  // Ze standardowego wejścia
  // odczytujemy:
  // n - liczbę wierzchołków
  //     w grafie sieci
  // m - liczbę krawędzi
  read(n, m);
  // Tworzymy dane dynamiczne
  //-------------------------
  // Tablica kolorów
  // wierzchołków
  SetLength(Color, n);
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    Color[i] := 0;
  end;
  // Macierz przepustowości
  // krawędzi
  SetLength(C, n+2);
  // Macierz przepływów netto
  SetLength(F, n+2);
  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;
  // Tablica poprzedników
  SetLength(P, n+2);
  // Tablica przepustowości
  // rezydualnych
  SetLength(CFP, n+2);
  // 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
        // Przeglądamy listę
        // sąsiadów wierzchołka
        // niebieskiego
        pr := graf[i];
        while pr <> nil do
        begin
          // Przepustowość krawędzi
          // do wierzchołka czerwonego
          C[i][pr^.data] := 1;
          // Następny sąsiad
          pr := pr^.next;
        end;
        // Przepustowość krawędzi
        // od źródła
        C[n][i] := 1;
      end
      else
        // Przepustowość krawędzi
        // do ujścia
        C[i][n+1] := 1;

    //*****************************
    //** 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
  //------------------------
  // Tablica kolorów wierzchołków
  SetLength(Color, 0);
  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;
  // Tablica list sąsiedztwa
  SetLength(graf, 0);
  for i := 0 to n+1 do
  begin
    SetLength(C[i], 0);
    SetLength(F[i], 0);
  end;
  // Macierz przepustowości
  // krawędzi
  SetLength(C, 0);
  // Macierz przepływów netto
  SetLength(F, 0);
  // Tablica poprzedników
  SetLength(P, 0);
  // Tablica przepustowości
  // rezydualnych
  SetLength(CFP, 0);
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 SLel
{
  SLel * next;
  int data;
};

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

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

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

// Konstruktor
//------------
queue::queue()
{
  head = tail = nullptr;
}

// Destruktor
//-----------
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)
{
  SLel * p = new SLel;
  p->next = nullptr;
  p->data = v;
  if(tail)
    tail->next = p;
  else
    head = p;
  tail = p;
}

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

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

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

// Funkcja zwraca true,
// jeśli graf jest dwudzielny.
// Ustala kolory wierzchołków
// w tablicy Color
//----------------------------
bool isBipartite()
{
  // Przechodzimy przez
  // kolejne wierzchołki
  for(int i = 0; i < n; i++)
    // Szukamy wierzchołka szarego
    if(!Color[i])
    {
      // Wierzchołek startowy
      // kolorujemy na czerwono
      Color[i] = 1;
      // i umieszczamy w kolejce
      Q.push(i);
      // Przejście BFS
      while(!Q.empty())
      {
        // Pobieramy wierzchołek
        // z kolejki
        v = Q.front();
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop();
        // Przeglądamy sąsiadów
        // wierzchołka v
        for(pr = graf[v];
            pr; pr = pr->next)
        {
          // pobieramy z listy
          // sąsiedztwa numer
          // sąsiada
          u = pr->data;
          if(Color[u] == Color[v])
            return false;
          // Jeśli wierzchołek nie
          // jest odwiedzony,
          if(!Color[u])
          {
            // kolorujemy go
            // na kolor przeciwny
            Color[u] = -Color[v];
            // i umieszczamy
            // w kolejce
            Q.push(u);
          }
        }
      }
    }
  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
  // Tablica kolorów wierzchołków
  Color = new int [n];
  // Tablica list sąsiedztwa
  graf = new SLel * [n];
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    Color[i] = 0;
  }
  // Macierz przepustowości
  //krawędzi
  C = new int * [n+2];
  // Macierz przepływów netto
  F = new int * [n+2];
  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++)
      F[i][j] = C[i][j] = 0;
  }
  // Tablica poprzedników
  P = new int [n+2];
  // Tablica przepustowości
  // rezydualnych
  CFP = new int [n+2];
  // Odczytujemy definicje
  // krawędzi i dodajemy
  // je do list sąsiedztwa
  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    pr = new SLel;
    pr->data = u;
    pr->next = graf[v];
    graf[v]  = pr;
    pr = new SLel;
    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)
      {
        // Przeglądamy listę
        // sąsiadów wierzchołka
        // niebieskiego
        for(pr = graf[i];
            pr; pr = pr->next)
          // Przepustowość krawędzi
          // do wierzchołka
          // czerwonego
          C[i][pr->data] = 1;
        // Przepustowość krawędzi
        // od źródła
        C[n][i] = 1;
      }
      else
        // Przepustowość krawędzi
        // do ujścia
        C[i][n+1] = 1;

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

    xfmax = 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)
            {
              xfmax += 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 = "
         << xfmax << endl << endl;
    if(xfmax > 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
  // Tablica kolorów wierzchołków
  delete [] Color;
  // Tablica list sąsiedztwa
  for(i = 0; i < n; i++)
  {
    pr = graf[i];
    while(pr)
    {
      rr = pr;
      pr = pr->next;
      delete rr;
    }
  }
  delete [] graf;
  for(i = 0; i <= n+1; i++)
  {
    delete [] C[i];
    delete [] F[i];
  }
  // Macierz przepustowości
  // krawędzi
  delete [] C;
  // Macierz przepływów netto
  delete [] F;
  // Tablica poprzedników
  delete [] P;
  // Tablica przepustowości
  // rezydualnych
  delete [] CFP;
  return 0;
}

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

Const MAXINT = 2147483647

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

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As SLel Ptr
    tail As SLel 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
'------------
Constructor queue
  head = 0
  tail = 0
End Constructor

' Destruktor
'-----------
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 SLel Ptr
  p = new SLel
  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 SLel Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

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

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

' Funkcja zwraca true,
' jeśli graf jest dwudzielny.
' Ustala kolory wierzchołków
' w tablicy Color
'---------------------------
Function isBipartite As Byte
  ' Przechodzimy przez
  ' kolejne wierzchołki
  For i = 0 To n-1
    ' Szukamy wierzchołka szarego
    If VColor[i] = 0 Then
      ' Wierzchołek startowy
      ' kolorujemy na czerwono
      VColor[i] = 1
      ' i umieszczamy w kolejce
      Q.push(i)
      ' Przejście BFS
      While Q.empty = 0
        ' Pobieramy wierzchołek z kolejki
        v = Q.front
        ' Pobrany wierzchołek
        ' usuwamy z kolejki
        Q.pop
        pr = graf[v]
        ' Przeglądamy sąsiadów
        ' wierzchołka v
        While pr <> 0
          ' pobieramy z listy
          ' sąsiedztwa numer sąsiada
          u = pr->data
          If VColor[u] = VColor[v] Then _
            return 0
          ' Jeśli wierzchołek
          ' nie jest odwiedzony,
          If VColor[u] = 0 Then 
            ' kolorujemy go
            ' na kolor przeciwny
            VColor[u] = -VColor[v]
            ' i umieszczamy w kolejce
            Q.push(u)
          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
' Tablica kolorów wierzchołków
VColor = New Integer [n]
' Tablica list sąsiedztwa
graf = New SLel Ptr [n]
For i = 0 To n-1
  graf[i] = 0
  VColor[i] = 0
Next
' Macierz przepustowości krawędzi
C = New Integer Ptr [n+2]
' Macierz przepływów netto
F = New Integer Ptr [n+2]
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
' Tablica poprzedników
P = New Integer [n+2]
' Tablica przepustowości rezydualnych
CFP = New Integer [n+2]
' Odczytujemy definicje krawędzi
' i dodajemy je do list sąsiedztwa
For i = 1 To m
  Input #1, v, u
  pr = New SLel
  pr->data = u
  pr->next = graf[v]
  graf[v]  = pr
  pr = New SLel
  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]
      ' Przeglądamy listę sąsiadów
      ' wierzchołka niebieskiego
      While pr <> 0
        ' Przepustowość krawędzi
        ' do wierzchołka czerwonego
        C[i][pr->data] = 1
        pr = pr->next
      Wend 
      ' Przepustowość krawędzi od źródła
      C[n][i] = 1
    Else
      ' Przepustowość krawędzi do ujścia
      C[i][n+1] = 1
    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
'------------------------
' Tablica kolorów wierzchołków
Delete [] VColor
For i = 0 To n-1
  pr = graf[i]
  While pr <> 0
    rr = pr
    pr = pr->next
    Delete rr
  Wend
Next
' Tablica list sąsiedztwa
Delete [] graf
For i = 0 To n+1
  Delete [] C[i]
  Delete [] F[i]
Next
' Macierz przepustowości krawędzi
Delete [] C
' Macierz przepływów netto
Delete [] F
' Tablica poprzedników
Delete [] P
' Tablica przepustowości rezydualnych
Delete [] CFP
End

# Maksymalne skojarzenia
# Data: 9.04.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

MAXINT = 2147483647

# Klasa elementów listy
class SLel:
    def __init__(self):
        self.next = None
        self.data = 0

# Klasa obiektu Queue
class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None

    # Destruktor
    def __del__(self):
        while not self.empty():
            self.pop()

    # Sprawdza,
    # czy kolejka jest pusta
    def empty(self):
        return not self.head

    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.data

    # Zapisuje do kolejki
    def push(self, v):
        p = SLel()
        p.next = None
        p.data = v
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p

    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None

#---------------
# Program główny
#---------------

# Kolejka
q = Queue()

# Funkcja zwraca true,
# jeśli graf jest dwudzielny.
# Ustala kolory wierzchołków
# w tablicy Color
def is_bipartite():
    global n,vcolor,q,graf
    # Przechodzimy przez
    # kolejne wierzchołki
    for i in range(n):
        # Szukamy wierzchołka szarego
        if not vcolor[i]:
            # Wierzchołek startowy
            # kolorujemy na czerwono
            vcolor[i] = 1
            # i umieszczamy w kolejce
            q.push(i)
            # Przejście BFS
            while not q.empty():
                # Pobieramy wierzchołek z kolejki
                v = q.front()
                # Pobrany wierzchołek
                # usuwamy z kolejki
                q.pop()
                pr = graf[v]
                # Przeglądamy sąsiadów
                # wierzchołka v
                while pr:
                    # pobieramy z listy
                    # sąsiedztwa numer sąsiada
                    u = pr.data
                    if vcolor[u] == vcolor[v]:
                        return False
                    # Jeśli wierzchołek
                    # nie jest odwiedzony,
                    if not vcolor[u]:
                        # kolorujemy go
                        # na kolor przeciwny
                        vcolor[u] = -vcolor[v]
                        # i umieszczamy w kolejce
                        q.push(u)
                    pr = pr.next
    return True

# Ze standardowego wejścia odczytujemy
# n — liczbę wierzchołków w grafie sieci
# m — liczbę krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy dane dynamiczne
# Tablica kolorów wierzchołków
vcolor = [0] * n
# Tablica list sąsiedztwa
graf = [None] * n
# Macierz przepustowości krawędzi
c = [[0 for j in range(n+2)] for i in range(n+2)]
# Macierz przepływów netto
f = [[0 for j in range(n+2)] for i in range(n+2)]
# Tablica poprzedników
p = [0] * (n+2)
# Tablica przepustowości rezydualnych
cfp = [0] * (n+2)
# Odczytujemy definicje krawędzi
# i dodajemy je do list sąsiedztwa
for i in range(m):
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    pr = SLel()
    pr.data = u
    pr.next = graf[v]
    graf[v] = pr
    pr = SLel()
    pr.data = v
    pr.next = graf[u]
    graf[u] = pr
if is_bipartite():
    # Ustawiamy macierz przepustowości
    for i in range(n):
        if vcolor[i] == -1:
            pr = graf[i]
            # Przeglądamy listę sąsiadów
            # wierzchołka niebieskiego
            while pr:
                # Przepustowość krawędzi
                # do wierzchołka czerwonego
                c[i][pr.data] = 1
                pr = pr.next
            # Przepustowość krawędzi od źródła
            c[n][i] = 1
        else:
            # Przepustowość krawędzi do ujścia
            c[i][n+1] = 1

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

    fmax = 0
    while True:
        for i in range(n+2):
            p[i] = -1
        p[n] = -2
        cfp[n] = MAXINT
        while not q.empty():
            q.pop()
        q.push(n)
        esc = False
        while not q.empty():
            v = q.front()
            q.pop()
            for u in range(n+2):
                cp = c[v][u] - f[v][u]
                if (cp > 0) and (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 not esc: break
    # Wyświetlamy wyniki
    print()
    print("NUMBER OF MATCHES =",fmax)
    print()
    if fmax > 0:
        for v in range(n):
            for u in range(n):
                if (c[v][u] == 1) and \
                   (f[v][u] == 1):
                    print(v,'-',u,sep="")
else:
    print()
    print("NOT A BIBARTITE GRAPH")
print()
# Usuwamy dane dynamiczne
#------------------------
# Tablica kolorów wierzchołków
del vcolor
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
# Tablica list sąsiedztwa
del graf
for i in range(n+2):
    c[i] = None
    f[i] = None
# Macierz przepustowości krawędzi
del c
# Macierz przepływów netto
del f
# Tablica poprzedników
del p
# Tablica przepustowości rezydualnych
del cfp