#include <stdio.h>

#define MAXN 100000	// Maximální počet vrcholů
#define MAXM 600000	// Maximální počet hran
#define INFTY 1000000000

/*
 *  Vrcholy sítě jsou očíslovány následovně:
 *
 *    0             zdroj
 *    1             spotřebič
 *    2 ... b+1     bachaři
 *    b+2 ... 2b+1  bloky věznice
 *
 *  Hrany jsou očíslovány od 2 (takže 0 může sloužit jako zarážka).
 *  Ke každé hraně e existuje hrana opačná s číslem e^1.
 */

int b;			// Počet bachařů a bloků
int m = 2;		// Počet hran
int dest[MAXM];		// Cílový vrchol
int cap[MAXM];		// Kapacita hrany
int flow[MAXM];		// Tok hranou
int first[MAXN];	// První hrana vedoucí z vrcholu
int next[MAXM];		// Další hrana vedoucí z téhož vrcholu
int flow_size;		// Aktuální velikost toku

// Přidá hranu (u,v) s kapacitou c
void adde(int u, int v, int c)
{
  dest[m] = v;
  cap[m] = c;
  flow[m] = 0;
  next[m] = first[u];
  first[u] = m;
  m++;
}

// Přidá hrany (u,v) a (v,u), první má kapacitu c, druhá 0
void add_edge(int u, int v, int c)
{
  adde(u, v, c);
  adde(v, u, 0);
}

// Načte vstup a vytvoří graf
void build_graph(void)
{
  int ne;
  scanf("%d%d", &b, &ne);

  // Původní hrany
  for (int i=0; i<ne; i++)
    {
      int u, v;
      scanf("%d%d", &u, &v);
      add_edge(2+u, b+2+v, 1);
    }

  // Hrany ze zdroje a do spotřebiče
  for (int i=0; i<b; i++)
    {
      add_edge(0, 2+i, 2);
      add_edge(b+2+i, 1, 2);
    }
}

int min(int x, int y)
{
  return (x < y) ? x : y;
}

// Jeden krok Forda-Fulkersona

int queue[MAXN];		// Fronta
int enter[MAXN];		// Kterou hranou jsme do vrcholu vstoupili
int best[MAXN];			// O kolik umíme zlepšit tok po cestě do daného vrcholu

int ff_step(void)
{
  for (int i=0; i<2*b+2; i++)	// Inicializace
    enter[i] = 0;
  best[0] = INFTY;

  queue[0] = 0;			// Na počátku je ve frontě jen zdroj
  int r=0, w=1;			// r = čtecí index fronty, w = zápisový index

  // Prohledávání do šířky
  for (;;)
    {
      if (r >= w)		// Nepodařilo se dojít do spotřebiče => tok je maximální
	return 0;
      int u = queue[r++];
      if (u == 1)
	break;
      for (int e=first[u]; e; e=next[e])		// Cyklus přes všechny hrany z u
	{
	  int v = dest[e];				// Hrana e = (u,v)
	  int res = cap[e] - flow[e] + flow[e^1];	// Její rezerva (o kolik lze zlepšit tok)
	  if (!enter[v] && res)
	    {
	      enter[v] = e;				// Ejhle, tady jsme ještě nebyli
	      best[v] = min(best[u], res);
	      queue[w++] = v;
	    }
	}
    }

  // Vracíme se po nalezené cestě ze spotřebiče do zdroje a zlepšujeme tok
  int u = 1;
  int delta = best[1];				// O kolik zlepšujeme
  while (u)
    {
      int e = enter[u];
      int d = min(delta, cap[e] - flow[e]);	// Zlepšení po směru
      flow[e] += d;
      flow[e^1] -= delta - d;			// Zlepšení proti směru
      u = dest[e^1];
    }
  flow_size += delta;
  return 1;
}

// Rozebrání nalezeného 2-faktoru na dvě párování

int out[MAXN][2];

void match(void)
{
  for (int i=0; i<b; i++)
    if (!out[2+i][0])
      {
	// Projdeme po cyklu: start je jeho první vrchol, u aktuální, p předchozí
	int start = 2+i;
	int u = start;
	int p = -1;
	do
	  {
	    for (int e=first[u]; e; e=next[e])
	      if (flow[e] || flow[e^1])		// Je to hrana 2-faktoru?
		{
		  int v = dest[e];
		  if (v >= 2)			// Vyhýbáme se zdroji a spotřebiči, ty na cyklech neleží
		    {
		      if (p < 0)
			p = v;
		      if (v != p)		// Hrany po směru procházení tvoří první párování, proti směru druhé
			out[u][0] = v;
		      else
			out[u][1] = v;
		    }
		}
	    p = u;
	    u = out[u][0];
	  }
	while (u != start);
      }
}

// Hlavní program

int main(void)
{
  build_graph();

  flow_size = 0;
  while (ff_step())
    ;
  if (flow_size < 2*b)
    {
      puts("Řešení neexistuje");
      return 1;
    }

  match();
  for (int i=0; i<b; i++)
    printf("%d %d\n", out[2+i][0] - (b+2), out[2+i][1] - (b+2));

  return 0;
}