using namespace std;
#include <stdio.h>
#include <vector>

#define Nmax 256
#define Mmax 7000

int N,M,i,minim,maxlvl,lung,x,y;
int m[Nmax][Nmax];
vector<int> G[Nmax];
int st[Nmax],st2[Nmax],bun[Nmax],grad[Nmax];
char w[Nmax];

void citire()
{
 freopen("strazi.in","r",stdin);
 scanf("%d %d",&N,&M);
 for (i=0;i<M;++i)
    {
     scanf("%d %d",&x,&y);
     G[x].push_back(y);
     m[x][y]=1;
     ++grad[y];
    }
 fclose(stdin);
}

void solutie(int nr)
{
 minim=nr;
 for (i=1;i<=N;++i)
    bun[i]=st[i];
}

void back(int nod,int lvl,int nr)
{
 int i;
 w[st[lvl]=nod]=1;
 if (lvl==N) if (nr<minim) { solutie(nr);w[nod]=0;return; }
   	         else { w[nod]=0;return; }
     else if (nr>=minim) { w[nod]=0;return; }
 for (i=1;i<=N;++i)
    if (!w[i])
      if (m[nod][i]) back(i,lvl+1,nr);
        else back(i,lvl+1,nr+1);
 w[nod]=0;
}

void dfs(int nod,int lvl)
{
 int i;
 vector<int>::iterator itt;
 w[st[lvl]=nod]=1;
 if (lvl>maxlvl)
   	{
         for (i=1;i<=lvl;++i)
            st2[i]=st[i];
         maxlvl=lvl;
        }
 for (i=0;i<G[nod].size();++i)
    if (!w[G[nod][i]]) dfs(G[nod][i],lvl+1);
 w[nod]=0;
}

void solve()
{
 int nod;
 minim=-2;
 while (1)
   {
    nod=0;
    ++minim;
    for (i=1;i<=N;++i)
       if ((!w[i])&&(grad[i]==0)) { nod=i;break; }
    if (nod==0) break;
    maxlvl=0;
    dfs(nod,1);
    for (i=1;i<=maxlvl;++i)
       {
        bun[++lung]=st2[i];
        w[st2[i]]=1;
       }
    for (nod=1;nod<=maxlvl;++nod)
	    for (i=0;i<G[st2[nod]].size();++i)
        	--grad[G[st2[nod]][i]];
   }
 printf("%d\n",minim);
 for (i=1;i<N;++i)
    if (!m[bun[i]][bun[i+1]]) printf("%d %d\n",bun[i],bun[i+1]);
 for (i=1;i<=N;++i)
    printf("%d ",bun[i]);
}

int main()
{
 freopen("strazi.out","w",stdout);
 citire();
 minim=2*N;
 if (N<=10)
   	{
         for (i=1;i<=N;++i) back(i,1,0);
         printf("%d\n",minim);
         for (i=1;i<N;++i)
            if (!m[bun[i]][bun[i+1]]) printf("%d %d\n",bun[i],bun[i+1]);
         for (i=1;i<=N;++i)
            printf("%d ",bun[i]);
        }
 	else solve();
 fclose(stdout);
 return 0;
}