// Kojarzenie małżeństw
// Data: 23.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

program perfmach;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz kolejki
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

    public
      constructor init;
      destructor  destroy;
      function    empty : boolean;
      function    front : integer;
      procedure   push (x : 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^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push (x : integer);
var
  p : PslistEl;
begin
  new (p);
  p^.next := nil;
  p^.v    := x;
  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
  n, m, i, v, x, y  : integer;
  color, visited    : array of boolean;
  matching, augment : array of integer;
  Q                 : queue;
  p, r              : PslistEl;
  graf              : TList;

begin
  read (n, m);             // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy zmienne dynamiczne

  SetLength (color, n);    // Kawalerowie (true), panny (false)
  SetLength (matching, n); // Skojarzenia
  SetLength (augment, n);  // Ścieżka rozszerzająca
  SetLength (visited, n);  // Odwiedziny
  Q.init;                    // Kolejka
  SetLength (graf, n);     // Tablica list sąsiedztwa

  // Tablice list sąsiedztwa wypełniamy pustymi listami

  for i := 0 to n - 1 do graf [i] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read (x, y);                // Krawędź panna --- kawaler
    new (p);                    // Tworzymy nowy element
    p^.v := y;                    // Numerujemy go jako kawaler
    p^.next := graf [x];        // Dodajemy go na początek listy panny
    graf [x] := p;
    new (p);                    // Tworzymy nowy element
    p^.v := x;                    // Numerujemy go jako pannę
    p^.next := graf [y];        // Dodajemy go na początek listy kawalera
    graf [y] := p;
    color [x] := false;         // Panna
    color [y] := true;          // Kawaler
  end;

  writeln;

  // Algorytm znajdowania maksymalnego skojarzenia

  for i := 0 to n - 1 do          // Elementy tablicy matching ustawiamy na -1
    matching [i] := -1;         // Co oznacza brak skojarzenia

  for v := 0 to n - 1 do          // Przechodzimy przez kolejne wierzchołki
    if(matching [v] = -1) and not color [v] then
    begin

      for i := 0 to n - 1 do
        visited [i] := false;   // Zerujemy tablicę odwiedzin

      while Q.empty = false do
        Q.pop;                    // Zerujemy kolejkę

      visited [v] := true;      // Oznaczamy v jako wierzchołek odwiedzony
      augment [v] := -1;        // Poprzednikiem v jest korzeń drzewa rozpinającego
      Q.push (v);               // Umieszczamy v w kolejce

      while Q.empty = false do    // Uruchamiamy BFS
      begin
        x := Q.front;             // Pobieramy x z kolejki
        Q.pop;                    // Pobrany wierzchołek usuwamy z kolejki

        if color [x] then
        begin                     // Kawalerowie
          if matching [x] = -1 then
          begin                   // Kawaler wolny
            while augment [x] > -1 do
            begin
              if color [x] then
              begin               // Zamieniamy krawędzie skojarzone z nieskojarzonymi
                matching [x] := augment [x];
                matching [augment [x]] := x;
              end;
              x := augment [x]; // Cofamy się po ścieżce rozszerzającej
            end;
            break;                // Wracamy do pętli głównej
          end
          else
          begin                   // Kawaler skojarzony
            augment [matching [x]] := x;
            visited [matching [x]] := true;
            Q.push (matching [x]); // W kolejce umieszczamy skojarzoną pannę
          end;
        end
        else
        begin                     // Panny
          p := graf [x];        // Przeglądamy kawalerów
          while p <> nil do
          begin
            y := p^.v;            // Numer kawalera
            if visited [y] = false then // Tylko kawalerowie nieskojarzeni
            begin                 // są umieszczani w kolejce
              visited [y] := true;
              augment [y] := x; // Tworzymy ścieżkę rozszerzającą
              Q.push (y);
            end;
            p := p^.next;
          end;
        end;
      end;
    end;

  // Wyświetlamy skojarzenia panna --- kawaler

  for i := 0 to n - 1 do
    if not color [i] then writeln(i, ' --- ', matching [i]);

  // Usuwamy dynamiczne struktury danych

  SetLength (color, 0);
  SetLength (matching, 0);
  SetLength (augment, 0);
  SetLength (visited, 0);
  Q.destroy;

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

  SetLength (graf, 0);

end.

// Kojarzenie małżeństw
// Data: 23.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

struct slistEl
{
  slistEl * next;
  int v;
};

const int MAXINT = -2147483647;

// 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 x);
    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->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push (int x)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v    = x;
  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 ***
// **********************

int main()
{
  int n, m, i, v, x, y, * matching, * augment;
  slistEl * p, * r, ** graf;
  bool * visited, * color;
  queue Q;

  cin >> n >> m;                  // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy zmienne dynamiczne

  color    = new bool [n];      // Kawalerowie (true), panny (false)
  matching = new int [n];       // Skojarzenia
  augment  = new int [n];       // Ścieżka rozszerzająca
  visited  = new bool [n];      // Odwiedziny
  graf     = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++) graf [i] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> x >> y;              // Krawędź panna --- kawaler
    p = new slistEl;            // Tworzymy nowy element
    p->v = y;                   // Numerujemy go jako kawaler
    p->next = graf [x];          // Dodajemy go na początek listy panny
    graf [x] = p;
    p = new slistEl;            // Tworzymy nowy element
    p->v = x;                   // Numerujemy go jako pannę
    p->next = graf [y];       // Dodajemy go na początek listy kawalera
    graf [y] = p;
    color [x] = false;        // Panna
    color [y] = true;         // Kawaler
  }

  cout << endl;

  // Algorytm znajdowania maksymalnego skojarzenia

  for(i = 0; i < n; i++)       // Elementy tablicy matching ustawiamy na -1
    matching [i] = -1;         // Co oznacza brak skojarzenia

  for(v = 0; v < n; v++)       // Przechodzimy przez kolejne wierzchołki
    if((matching [v] == -1) && !color [v])
    {
      for(i = 0; i < n; i++)
        visited [i] = false;   // Zerujemy tablicę odwiedzin

      while(!Q.empty()) Q.pop(); // Zerujemy kolejkę

      visited [v] = true;      // Oznaczamy v jako wierzchołek odwiedzony
      augment [v] = -1;        // Poprzednikiem v jest korzeń drzewa rozpinającego
      Q.push (v);              // Umieszczamy v w kolejce

      while(!Q.empty())       // Uruchamiamy BFS
      {
        x = Q.front();          // Pobieramy x z kolejki
        Q.pop();                // Pobrany wierzchołek usuwamy z kolejki

        if(color [x])
        {                        // Kawalerowie
          if(matching [x] == -1)
          {                      // Kawaler wolny
            while(augment [x] > -1)
            {
              if(color [x])
              {                  // Zamieniamy krawędzie skojarzone z nieskojarzonymi
                matching [x] = augment [x];
                matching [augment [x]] = x;
              }
              x = augment [x]; // Cofamy się po ścieżce rozszerzającej
            }
            break;               // Wracamy do pętli głównej
          }
          else
          {                      // Kawaler skojarzony
            augment [matching [x]] = x;
            visited [matching [x]] = true;
            Q.push (matching [x]); // W kolejce umieszczamy skojarzoną pannę
          }
        }
        else
        {                        // Panny
          p = graf [x];        // Przeglądamy kawalerów
          while(p)
          {
            y = p->v;            // Numer kawalera
            if(!visited [y]) // Tylko kawalerowie nieskojarzeni
            {                    // są umieszczani w kolejce
              visited [y] = true;
              augment [y] = x; // Tworzymy ścieżkę rozszerzającą
              Q.push (y);
            }
            p = p->next;
          }
        }
      }
    }

  // Wyświetlamy skojarzenia panna --- kawaler

  for(i = 0; i < n; i++)
    if(!color [i]) cout << i << " --- " << matching [i] << endl;

  // Usuwamy dynamiczne struktury danych

  delete [] color;
  delete [] matching;
  delete [] augment;
  delete [] visited;

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

  delete [] graf;

  return 0;}

' Kojarzenie małżeństw
' Data: 23.12.2013
' (C)2013 mgr Jerzy Wałaszek
'----------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Const MAXINT = 2147483647

' 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->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal x As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = x
  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 As Integer n, m, i, v, x, y
Dim As slistEl Ptr p, r
Dim As slistEl Ptr Ptr graf
Dim As Integer Ptr visited, matching, augment, ccolor
Dim As queue Q

Open Cons For Input As #1

Input #1, n, m            ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy zmienne dynamiczne

ccolor   = New Integer [n]     ' Kawalerowie (true), panny (false)
matching = New Integer [n]     ' Skojarzenia
augment  = New Integer [n]     ' Ścieżka rozszerzająca
visited  = New Integer [n]     ' Odwiedziny
graf     = New slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  graf [i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1, x, y            ' Krawędź panna --- kawaler
  p = New slistEl           ' Tworzymy nowy element
  p->v = y                  ' Numerujemy go jako kawaler
  p->next = graf [x]      ' Dodajemy go na początek listy panny
  graf [x] = p
  p = new slistEl           ' Tworzymy nowy element
  p->v = x                  ' Numerujemy go jako pannę
  p->next = graf [y]      ' Dodajemy go na początek listy kawalera
  graf [y] = p
  ccolor [x] = 0          ' Panna
  ccolor [y] = 1          ' Kawaler
Next

Close #1

Print

' Algorytm znajdowania maksymalnego skojarzenia

For i = 0 To n - 1                ' Elementy tablicy matching ustawiamy na -1
  matching [i] = -1             ' Co oznacza brak skojarzenia
Next

For v = 0 To n - 1                ' Przechodzimy przez kolejne wierzchołki
  if(matching [v] = -1) AndAlso (ccolor [v] = 0) Then
    For i = 0 To n - 1
      visited [i] = 0           ' Zerujemy tablicę odwiedzin
    Next
   
    While Q.empty() = 0
      Q.pop()                    ' Zerujemy kolejkę
    Wend

    visited [v] = 1             ' Oznaczamy v jako wierzchołek odwiedzony
    augment [v] = -1            ' Poprzednikiem v jest korzeń drzewa rozpinającego
    Q.push (v)                  ' Umieszczamy v w kolejce

    While Q.empty() = 0          ' Uruchamiamy BFS
      x = Q.front()              ' Pobieramy x z kolejki
      Q.pop()                    ' Pobrany wierzchołek usuwamy z kolejki

      If ccolor [x] = 1 Then    ' Kawalerowie
        If matching [x] = -1 Then  ' Kawaler wolny         
          While augment [x] > -1
            If ccolor [x] = 1 Then ' Zamieniamy krawędzie skojarzone z nieskojarzonymi
              matching [x] = augment [x]
              matching [augment [x]] = x
            End If
            x = augment [x]     ' Cofamy się po ścieżce rozszerzającej
          Wend
          Exit While              ' Wracamy do pętli głównej
        Else                      ' Kawaler skojarzony
          augment [matching [x]] = x
          visited [matching [x]] = 1
          Q.push (matching [x]) ' W kolejce umieszczamy skojarzoną pannę
        End If
      Else                        ' Panny
        p = graf [x]            ' Przeglądamy kawalerów
        While p
          y = p->v                ' Numer kawalera
          If visited [y] = 0 Then  ' Tylko kawalerowie nieskojarzeni
            visited [y] = 1     ' są umieszczani w kolejce
            augment [y] = x     ' Tworzymy ścieżkę rozszerzającą
            Q.push (y)
          End If
          p = p->Next
        Wend
      End If
    Wend
  End If
Next

' Wyświetlamy skojarzenia panna --- kawaler

For i = 0 To n - 1
  If ccolor [i] = 0 then Print i;" ---";matching [i]
Next

' Usuwamy dynamiczne struktury danych

Delete [] ccolor
Delete [] matching
Delete [] augment
Delete [] visited
 
For i = 0 To n - 1
  p = graf [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

End