#include <stdio.h>
#include <vector>

using namespace std;

#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second

vector< pair<int,int> > sol;

long int a[20][20],i,j,k,n,m,x,y;
long int st[20],ord[20],ret,uz[20];

void back(long int nivel)
{
long int i,k;
if (nivel==n+1)
        {
        k=0;
        for (i=1;i<n;i++) if (!a[st[i]][st[i+1]]) k++;
        
        if (k<ret)
                {
                ret=k;
                vector< pair<int,int> >().swap(sol);
                for (i=1;i<n;i++)
                        {
                        ord[i]=st[i];
                        if (!a[st[i]][st[i+1]]) sol.pb( mp(st[i],st[i+1]) );
                        }
                ord[n]=st[n];
                }
        return;
        }

for (i=1;i<=n;i++)
        if (!uz[i])
                {
                st[nivel]=i;
                uz[i]=1;
                back(nivel+1);
                uz[i]=0;
                }
}

int main()
{
freopen("strazi.in","r",stdin);
freopen("strazi.out","w",stdout);

scanf("%ld %ld",&n,&m);

for (i=1;i<=m;i++)
        {
        scanf("%ld %ld",&x,&y);
        a[x][y]=1;
        }

ret=10000000;
back(1);
printf("%ld\n",ret);
for (i=0;i<sol.sz;i++)
        printf("%ld %ld\n",sol[i].ff,sol[i].ss);

for (i=1;i<=n;i++)
        printf("%ld ",ord[i]);
return 0;
}