#include <iostream>
#include <fstream>

using namespace std;

#define IN "strazi.in"
#define OUT "strazi.out"

ifstream fin(IN);
ofstream fout(OUT);

#define maxx 260

int n,m;
int a[maxx][maxx];
int c[maxx];

int viz[maxx];
int l[maxx];

int minim;
int sww=1;

struct solutie
{
 int c1;
 int c2;
}sol[maxx];

void citire();
void afis();
int merge();
void lant(int x);
int nefol();
void adauga();

int main()
{
 int sw=1;
 int i;
 int p;
 
 citire();
  fin.close();

 sww=1;
 lant(1);

 for(i=1;i<=l[0];i++)
 {
  c[0]++;
  c[c[0]]=l[i];
 }
 
 while(sw)
 {
  memset(l,0,sizeof(l));
  
  p=nefol();

  sww=1;
  lant(p);

  adauga();

  sw=merge();
 }

 afis();
  fout.close();
  
return 0;
}

void citire()
{
 int i;
 int x,y;

 fin>>n>>m;

 for(i=1;i<=m;i++)
 {
  fin>>x;
  fin>>y;
  a[x][y]=1;
 }
}

void afis()
{
 int i;

 fout<<minim<<endl;
  for(i=1;i<=minim;i++)
   fout<<sol[i].c1<<" "<<sol[i].c2<<endl;

 for(i=1;i<=n;i++)
  fout<<c[i]<<" ";

 fout<<endl;
}

int merge()
{
 int i;

 for(i=1;i<=n;i++)
  if(viz[i]==0)
   return 1;
   
return 0;
}

void lant(int x)
{
 int i;

 if(sww==0)
  return;
 
 l[0]++;
 l[l[0]]=x;
 viz[x]=1;

 for(i=1;i<=n;i++)
  if(a[x][i]==1 && viz[i]==0)
  {
   a[x][i]=0;
   lant(i);
  }
 sww=0;
}

int nefol()
{
 int i;

 for(i=1;i<=n;i++)
  if(viz[i]==0)
   return i;
   
return 0;
}

void adauga()
{
 //// am gasit lant
 //// unsec si memorez sol

 minim++;
 sol[minim].c1=c[c[0]];
 sol[minim].c2=l[1];

 int i;

 for(i=1;i<=l[0];i++)
 {
  c[0]++;
  c[c[0]]=l[i];
 }

}