// 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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

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

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

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

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy zmienne dynamiczne
  //----------------------------
  // Kawalerowie (true),
  // panny (false)
  SetLength(color, n);
  // Skojarzenia
  SetLength(matching, n);
  // Ścieżka rozszerzająca
  SetLength(augment, n);
  // Odwiedziny
  SetLength(vs, n);
  // Kolejka
  Q.init;
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  // 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
    // Krawędź panna-kawaler
    read(x, y);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako kawaler
    p^.v := y;
    // Dodajemy go na początek
    // listy panny
    p^.next := graf[x];
    graf[x] := p;
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako pannę
    p^.v := x;
    // Dodajemy go na początek
    // listy kawalera
    p^.next := graf[y];
    graf[y] := p;
    // Panna
    color[x] := false;
    // Kawaler
    color[y] := true;
  end;
  writeln;
  // Algorytm znajdowania
  // maksymalnego skojarzenia
  //-------------------------
  // Elementy tablicy matching
  // ustawiamy na -1,
  // co oznacza brak skojarzenia
  for i := 0 to n-1 do
    matching[i] := -1;
  // Przechodzimy przez
  // kolejne wierzchołki
  for v := 0 to n-1 do
    if (matching[v] = -1) and
        not color[v] then
    begin
      for i := 0 to n-1 do
        // Zerujemy tablicę odwiedzin
        vs[i] := false;
      while not Q.empty do
        // Zerujemy kolejkę
        Q.pop;
      // Oznaczamy v jako
      // wierzchołek odwiedzony
      vs[v] := true;
      // Poprzednikiem v jest
      // korzeń drzewa rozpinającego
      augment[v] := -1;
      // Umieszczamy v w kolejce
      Q.push(v);
      // Uruchamiamy BFS
      while Q.empty = false do
      begin
        // Pobieramy x z kolejki
        x := Q.front;
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop;
        if color[x] then
        // Kawalerowie
        begin
          if matching[x] = -1 then
          // Kawaler wolny
          begin
            while augment[x] > -1 do
            begin
              if color[x] then
              // Zamieniamy krawędzie
              // skojarzone
              // z nieskojarzonymi
              begin
                matching[x] := augment[x];
                matching[augment[x]] := x;
              end;
              // Cofamy się po ścieżce
              // rozszerzającej
              x := augment[x];
            end;
            // Wracamy do pętli głównej
            break;
          end
          else
          // Kawaler skojarzony
          begin
            augment[matching[x]] := x;
            vs[matching[x]] := true;
            // W kolejce umieszczamy
            // skojarzoną pannę
            Q.push(matching[x]);
          end;
        end
        else
        // Panny
        begin
          // Przeglądamy kawalerów
          p := graf[x];
          while p <> nil do
          begin
            // Numer kawalera
            y := p^.v;
            // Tylko kawalerowie
            // nieskojarzeni
            if vs[y] = false then
            // są umieszczani w kolejce
            begin
              vs[y] := true;
              // Tworzymy ścieżkę
              // rozszerzającą
              augment[y] := x;
              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(vs, 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 SLel
{
  SLel * next;
  int v;
};

const int MAXINT = 2147483647;

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

  public:
    queue(); // konstruktor
    ~queue(); // destruktor
    bool empty(void);
    int  front(void);
    void push(int x);
    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->v;
  else     return -MAXINT;
}

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

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy zmienne dynamiczne
  //----------------------------
  // Kawalerowie (true),
  // panny (false)
  color = new bool [n];
  // Skojarzenia
  matching = new int [n];
  // Ścieżka rozszerzająca
  augment = new int [n];
  // Odwiedziny
  vs = new bool [n];
  // Tworzymy tablicę
  // list sąsiedztwa
  graf = new SLel * [n];
  // Tablicę wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    graf[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Krawędź panna-kawaler
    cin >> x >> y;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako kawaler
    p->v = y;
    // Dodajemy go
    // na początek listy panny
    p->next = graf[x];
    graf[x] = p;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako pannę
    p->v = x;
    // Dodajemy go na początek
    // listy kawalera
    p->next = graf[y];
    graf[y] = p;
    color[x] = false; // Panna
    color[y] = true; // Kawaler
  }
  cout << endl;
  // Algorytm znajdowania
  // maksymalnego skojarzenia
  //-------------------------
  // Elementy tablicy matching
  // ustawiamy na -1
  for(i = 0; i < n; i++)
    // Co oznacza brak skojarzenia
    matching[i] = -1;
  // Przechodzimy przez
  // kolejne wierzchołki
  for(v = 0; v < n; v++)
    if((matching[v] == -1) &&
       !color[v])
    {
      for(i = 0; i < n; i++)
        // Zerujemy
        // tablicę odwiedzin
        vs[i] = false;
      while(!Q.empty())
        // Zerujemy kolejkę
        Q.pop();
      // Oznaczamy v jako
      // wierzchołek odwiedzony
      vs[v] = true;
      // Poprzednikiem v jest
      // korzeń drzewa rozpinającego
      augment[v] = -1;
      // Umieszczamy v w kolejce
      Q.push(v);
      // Uruchamiamy BFS
      while(!Q.empty())
      {
        // Pobieramy x z kolejki
        x = Q.front();
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop();
        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;
              }
              // Cofamy się po ścieżce
              // rozszerzającej
              x = augment[x];
            }
            // Wracamy do pętli głównej
            break;
          }
          else
          // Kawaler skojarzony
          {
            augment[matching[x]] = x;
            vs[matching[x]] = true;
            // W kolejce umieszczamy
            // skojarzoną pannę
            Q.push(matching[x]);
          }
        }
        else
        // Panny
        {
          // Przeglądamy kawalerów
          p = graf[x];
          while(p)
          {
            // Numer kawalera
            y = p->v;
            // Tylko kawalerowie
            // nieskojarzeni
            if(!vs[y])
            // są umieszczani
            // w kolejce
            {
              vs[y] = true;
              // Tworzymy
              // ścieżkę rozszerzającą
              augment[y] = x;
              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 [] vs;
  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 SLel
  next As SLel Ptr
  v As Integer
End Type

Const MAXINT = 2147483647

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

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal x As Integer)
  Dim p As SLel Ptr
  p = new SLel
  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 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 ***
' **********************

Dim As Integer n, m, i, v, x, y
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr graf
Dim As Integer Ptr vs, matching, _
                   augment, ccolor
Dim As queue Q

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy zmienne dynamiczne
'----------------------------
' Kawalerowie (true), panny (false)
ccolor = New Integer [n]
' Skojarzenia
matching = New Integer [n]
' Ścieżka rozszerzająca
augment = New Integer [n]
' Odwiedziny
vs = New Integer [n]
' Tworzymy tablicę list sąsiedztwa
graf = New SLel Ptr [n]
' 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
  ' Krawędź panna-kawaler
  Input #1, x, y
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako kawaler
  p->v = y
  ' Dodajemy go na początek listy panny
  p->next = graf[x]
  graf[x] = p
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako pannę
  p->v = x
  ' Dodajemy go na początek
  ' listy kawalera
  p->next = graf[y]
  graf[y] = p
  ccolor[x] = 0 ' Panna
  ccolor[y] = 1 ' Kawaler
Next
Close #1
Print
' Algorytm znajdowania
' maksymalnego skojarzenia
'-------------------------
' Elementy tablicy matching
' ustawiamy na -1
For i = 0 To n-1
  ' Co oznacza brak skojarzenia
  matching[i] = -1
Next
' Przechodzimy przez kolejne wierzchołki
For v = 0 To n-1
  If (matching[v] = -1) AndAlso _
     (ccolor[v] = 0) Then
    For i = 0 To n-1
      ' Zerujemy tablicę odwiedzin
      vs[i] = 0
    Next
    While Q.empty = 0
      ' Zerujemy kolejkę
      Q.pop
    Wend
    ' Oznaczamy v jako
    ' wierzchołek odwiedzony
    vs[v] = 1
    ' Poprzednikiem v jest korzeń
    ' drzewa rozpinającego
    augment[v] = -1
    ' Umieszczamy v w kolejce
    Q.push(v)
    ' Uruchamiamy BFS
    While Q.empty = 0
      ' Pobieramy x z kolejki
      x = Q.front
      ' Pobrany wierzchołek
      ' usuwamy z kolejki
      Q.pop
      ' Kawalerowie
      If ccolor[x] = 1 Then
        ' Kawaler wolny
        If matching[x] = -1 Then
          While augment[x] > -1
            ' Zamieniamy krawędzie
            ' skojarzone
            ' z nieskojarzonymi
            If ccolor[x] = 1 Then
              matching[x] = augment[x]
              matching[augment[x]] = x
            End If
            ' Cofamy się
            ' po ścieżce rozszerzającej
            x = augment[x]
          Wend
          ' Wracamy do pętli głównej
          Exit While
        ' Kawaler skojarzony
        Else
          augment[matching[x]] = x
          vs[matching[x]] = 1
          ' W kolejce umieszczamy
          ' skojarzoną pannę
          Q.push(matching[x])
        End If
      Else ' Panny
        ' Przeglądamy kawalerów
        p = graf[x]
        While p
          ' Numer kawalera
          y = p->v
          ' Tylko kawalerowie
          ' nieskojarzeni
          If vs[y] = 0 Then
            ' są umieszczani w kolejce
            vs[y] = 1
            ' Tworzymy
            ' ścieżkę rozszerzającą
            augment[y] = x
            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 [] vs
For i = 0 To n-1
  p = graf[i]
  While p
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] graf
End

# Kojarzenie małżeństw
# Data: 23.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa dla dynamicznej tablicy list
# sąsiedztwa i kolejki
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

MAXINT = 2147483647

# Definicja typu obiektowego 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):
        if not self.head: return True
        return False


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


    # Zapisuje do kolejki
    def push(self, x):
        p = SLel()
        p.next = None
        p.v = x
        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 ***
# **********************

q = Queue()
# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zmienne dynamiczne
#----------------------------
# Kawalerowie (true), panny (false)
ccolor = [False] * n
# Skojarzenia
matching = [-1] * n
# Ścieżka rozszerzająca
augment = [0] * n
# Odwiedziny
vs = [False] * n
# Tworzymy tablicę list sąsiedztwa
graf = [None] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Krawędź panna-kawaler
    xx = input().split()
    x = int(xx[0])
    y = int(xx[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako kawaler
    p.v = y
    # Dodajemy go na początek listy panny
    p.next = graf[x]
    graf[x] = p
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako pannę
    p.v = x
    # Dodajemy go na początek
    # listy kawalera
    p.next = graf[y]
    graf[y] = p
    ccolor[x] = False # Panna
    ccolor[y] = True # Kawaler
print()
# Algorytm znajdowania
# maksymalnego skojarzenia
#-------------------------
# Przechodzimy przez kolejne wierzchołki
for v in range(n):
    if (matching[v] == -1) and \
         not ccolor[v]:
        for i in range(n):
            # Zerujemy tablicę odwiedzin
            vs[i] = False
        while not q.empty():
            # Zerujemy kolejkę
            q.pop()
        # Oznaczamy v jako
        # wierzchołek odwiedzony
        vs[v] = True
        # Poprzednikiem v jest korzeń
        # drzewa rozpinającego
        augment[v] = -1
        # Umieszczamy v w kolejce
        q.push(v)
        # Uruchamiamy BFS
        while not q.empty():
            # Pobieramy x z kolejki
            x = q.front()
            # Pobrany wierzchołek
            # usuwamy z kolejki
            q.pop()
            # Kawalerowie
            if ccolor[x]:
                # Kawaler wolny
                if matching[x] == -1:
                    while augment[x] > -1:
                        # Zamieniamy krawędzie
                        # skojarzone
                        # z nieskojarzonymi
                        if ccolor[x]:
                            matching[x] = augment[x]
                            matching[augment[x]] = x
                        # Cofamy się
                        # po ścieżce rozszerzającej
                        x = augment[x]
                    # Wracamy do pętli głównej
                    break
                # Kawaler skojarzony
                else:
                    augment[matching[x]] = x
                    vs[matching[x]] = True
                    # W kolejce umieszczamy
                    # skojarzoną pannę
                    q.push(matching[x])
            else: # Panny
                # Przeglądamy kawalerów
                p = graf[x]
                while p:
                    # Numer kawalera
                    y = p.v
                    # Tylko kawalerowie
                    # nieskojarzeni
                    if not vs[y]:
                        # są umieszczani w kolejce
                        vs[y] = True
                        # Tworzymy
                        # ścieżkę rozszerzającą
                        augment[y] = x
                        q.push(y)
                    p = p.next
# Wyświetlamy skojarzenia panna-kawaler
for i in range(n):
    if not ccolor[i]:
        print(i,"---",matching[i])
# Usuwamy dynamiczne struktury danych
del ccolor, matching, augment, vs
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf