#include <string.h>
#include <fstream>
#include <vector>

#define maxN 256

using namespace std;

vector <int> g[maxN];

int T[maxN];
int w[maxN];
int add=0x7fffffff;
int N;
int e[maxN][maxN];

inline void dfs(int nod,int cnt,int sel,int use[])
{
    int v[maxN];

    if(sel==N)
    {
        if(cnt<add)
        {
            add=cnt;
            for(int i=1;i<=N;++i) w[i]=T[i];
            w[1]=nod;
        }
    }

    use[nod]=1;

    int ok=0;
    for(vector <int>::iterator it=g[nod].begin();it!=g[nod].end();++it)
        if(!use[*it])
        {
            T[*it]=nod;
            ok=1;

            for(int i=1;i<=N;++i) v[i]=use[i];
            dfs(*it,cnt,sel+1,v);
        }

    if(ok==0)
        for(int i=1;i<=N;++i)
            if(!use[i])
            {
                for(int j=1;j<=N;++j) v[j]=use[j];

                T[i]=nod;
                dfs(i,cnt+1,sel+1,v);
            }
}

ifstream in;
ofstream out;

int main()
{
    int M,x,y;

    in.open("strazi.in");

    in>>N>>M;

    memset(e,0,sizeof(e));
    while(M--)
    {
        in>>x>>y;
        g[x].push_back(y);
        e[x][y]=1;
    }

    in.close();

    int use[maxN];
    memset(use,0,sizeof(use));
    dfs(1,0,1,use);

    out.open("strazi.out");

    out<<add<<'\n';

    for(int i=2;i<=N;++i)
        if(e[w[i]][i]==0) out<<w[i]<<' '<<i<<'\n';

    memset(T,0,sizeof(T));
    int nod=w[1];
    T[0]=1;
    T[1]=1;
    while(nod!=1)
    {
        T[++T[0]]=nod;
        nod=w[nod];
    }

    for(int i=T[0];i>0;--i) out<<T[i]<<' ';
    out<<'\n';

    out.close();

    return 0;
}