/*
 *
 *
  preONI 2008 - Runda 3 - Strazi
 *
 *
 */

#include<stdio.h>
#include<string.h>

#define INPUT "strazi.in"
#define OUTPUT "strazi.out"

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

int nrNod, nrMuch, leg[256][256];
int adancimeTotal, adancimeNoua, pozINoua, pozFNoua, util[256];
int stiva[1000],pozSt,pozFin,valAdn,pozAdn,adanc[256],tata[256],ordine,ordineFinala[256],final[256],vect[256];
int pozStrada[256][2], nrTotalStrazi,gh;

void readValues();
void solveFunction();
void parcurge(int, int &, int &);
void afisRez();

int main()
{
  nrTotalStrazi=0;
  readValues();
  solveFunction();
  afisRez();
  fclose(fin);
  fclose(fout);
  return 0;
}

void readValues()
{
  int val1, val2;
  fscanf(fin, "%d %d", &nrNod, &nrMuch);
  for(int i=1;i<=nrMuch;++i)
  {
    fscanf(fin, "%d %d", &val1, &val2);
    leg[val1][val2] =  1;
  }
}

void solveFunction()
{
  int adancime, pozF,k;
  adancimeTotal = 0;
  ordine=1;
  gh=1;
  while(adancimeTotal<nrNod)
  {
    adancimeNoua = -1;
    pozINoua = 0;
    pozFNoua = 0;
    for(int i=1;i<=nrNod;++i)
    {
      if(!util[i])
      {
	parcurge(i, adancime, pozF);
	if(adancimeNoua<adancime){
	  adancimeNoua = adancime;
	  pozINoua = i;
	  pozFNoua = pozF;
	  memset(final,0,sizeof(final));
	  for(int j=1;j<=adancimeNoua+1;++j)
	    final[j]=vect[j];
	}
      }
    }
    if(ordine!=1)
    {
      pozStrada[gh][1]=ordineFinala[ordine-1];
      pozStrada[gh][2]=final[adancimeNoua+1];
      ++nrTotalStrazi;
    }
    for(int i=adancimeNoua+1;i>=1;--i){
      ordineFinala[ordine]=final[i];
      util[final[i]]=1;
      ++ordine;
    }
    adancimeTotal +=adancimeNoua;
    ++adancimeTotal;
  }
}

void parcurge(int val1, int &val2, int &val3){
  int utilSec[256];
  int utilTert[256];
  int tmp = 0;
  memset(adanc,0, sizeof(adanc));
  memset(stiva, 0, sizeof(stiva));
  memset(tata, 0, sizeof(tata));
  memset(utilTert, 0, sizeof(utilTert));
  stiva[1]=val1;
  utilTert[stiva[1]]=1;
  pozSt = 1;
  pozFin = 1;
  while(pozSt<=pozFin){
    tmp = 1;
    for(int i=1;i<=nrNod;++i){
      if(leg[stiva[pozSt]][i]==1 && adanc[stiva[pozSt]]+1>adanc[i] && !util[i] && !utilTert[i]){
	++pozFin;
	stiva[pozFin]=i;
	utilTert[stiva[pozFin]]=1;
	adanc[i]=adanc[stiva[pozSt]]+1;
	tata[i]=stiva[pozSt];
	tmp = 0;
      }
    }
    if(tmp==1){
      utilTert[stiva[pozSt]]=0;
    }
    ++pozSt;
  }
  valAdn = -1;
  pozAdn = -1;
  for(int i=1;i<=nrNod;++i){
    if(valAdn < adanc[i]){
      valAdn = adanc[i];
      pozAdn = i;
    }
  }
  if(valAdn!=0){
  val2 = valAdn;
  val3 = pozAdn;
  }
  else{
  val2 = 0;
  val3 = stiva[1];
  pozAdn = stiva[1];
  }
  memset(vect, 0, sizeof(vect));
  int j=1;
  memset(utilSec, 0, sizeof(utilSec));
  while(pozAdn!=0 && utilSec[pozAdn]!=1){
    vect[j]=pozAdn;
    utilSec[pozAdn]=1;
    ++j;
    pozAdn = tata[pozAdn];
  }
}

void afisRez(){
  fprintf(fout, "%d\n", nrTotalStrazi);
  for(int i=1;i<=nrTotalStrazi;++i){
    fprintf(fout, "%d %d\n", pozStrada[i][1], pozStrada[i][2]);
  }
  for(int i=1;i<=nrNod;++i){
    fprintf(fout, "%d ", ordineFinala[i]);
  }
  fprintf(fout, "\n");
}