#include <fstream>
#include <string>
#define nmax 300
using namespace std;
ifstream f("strazi.in");
ofstream g("strazi.out");
int n,m;
int drum[nmax],gr[nmax],in[nmax],Q[nmax],k;
int pre[nmax];
int tur[nmax],tr;
bool viz[nmax],viz2[nmax];
bool ok[nmax][nmax];
struct graf
 {
 graf *urm;
 int x;
 };
graf *G[nmax];
#define G (G-1)
void add(graf *&g,int x)
 {
 graf *p=new graf;
 p->x=x;
 p->urm=g;
 g=p;
 }
int grx[nmax],inx[nmax];
void msort(int l,int r)
 {
 if(l==r) return;
 int mj=(l+r)/2;
 msort(l,mj);
 msort(mj+1,r);
 int i,j,k;
 for(i=l,j=mj+1,k=l-1;i<=mj||j<=r;)
  {
  if(j>r||(i<=mj&&gr[i]<gr[j]))
   {
   grx[++k]=gr[i];
   inx[k]=in[i++];
   }
  else
   {
   grx[++k]=gr[j];
   inx[k]=in[j++];
   }
  }
 for(i=l;i<=r;++i){in[i]=inx[i];gr[i]=grx[i];}
 }
void read()
 {
 f>>n>>m;
 int i,x,y;
 for(i=1;i<=m;i++)
  {
  f>>x>>y;
  ++gr[y];
  add(G[x],y);
  ok[x][y]=true;
  }
 for(i=1;i<=n;i++) in[i]=i;
 }
void bfs(int nod)
 {
 k=0;
 Q[++k]=nod;
 
 int i,x,pz,pmax;
 pmax=1;
 pz=nod;
 memset(viz2,false,sizeof(viz2));
 memset(drum,0,sizeof(drum));
 memset(pre,0,sizeof(pre));
 drum[nod]=1;
 for(i=1;i<=k;i++)
  {
  x=Q[i];
  for(graf *g=G[x];g!=NULL;g=g->urm)
   {
   if(!viz[g->x])
    {
    //viz2[g->x]=true;
	drum[g->x]=drum[x]+1;
	Q[++k]=g->x;
	pre[g->x]=x;
	if(drum[g->x]>pmax)
	 {
	 pmax=drum[g->x];
	 pz=g->x;
	 }
    }	   
   }
  }
 tr+=pmax;
 for(x=pz;x!=0;x=pre[x])
  {
  viz[x]=true;
  tur[tr-(drum[pz]-drum[x])]=x;
  }
 }
void show()
 {
 int nsol=0,i;
 for(i=1;i<n;i++)
  {
  if(!ok[tur[i]][tur[i+1]])
   ++nsol;
  }
 g<<nsol<<endl;
 for(i=1;i<n;i++)
  {
  if(!ok[tur[i]][tur[i+1]])
   g<<tur[i]<<" "<<tur[i+1]<<" ";
  }
 g<<endl;
 for(i=1;i<=n;i++) g<<tur[i]<<" ";
 }
int main()
 {
 int i;
 read();
 msort(1,n);
 for(i=1;i<=n;i++)
  {
  if(!viz[in[i]])
   bfs(in[i]);
  }
 show();
 return 0;
 }