#include <stdio.h>
#define NMAX 256

#define MIN(a,b) (((a)<(b))?(a):(b))

int A[NMAX][NMAX], C[NMAX][NMAX], N, M, min = 666000666, nsol, Sol[NMAX];
int Mark[NMAX][NMAX], St[NMAX][NMAX], nr[NMAX], V[NMAX];

void greedy()
{
        int i, j, s, stiva;

        for (s = 1; s <= N; s++)
        {
                memset(nr,0,sizeof(nr));
                memset(C,0,sizeof(C));
                memset(Mark,0,sizeof(Mark));
                for (stiva = 1; stiva <= N; stiva++)
                    if (stiva!=s)
                    {
                       St[stiva][ nr[stiva]++ ] = s, Mark[stiva][s] = 1;
                       St[stiva][ nr[stiva]++ ] = stiva, Mark[stiva][stiva] = 1;
                       C[stiva][ nr[stiva]-1 ] = (A[s][stiva]+1)&1;
                    }
                for (stiva = 1; stiva <= N; stiva++)
                    if (stiva!=s)
                    {
                        i = St[stiva][ nr[stiva]-1 ];
                        for (j = 1; j <= N && nr[stiva] < N; j++)
                            if (!Mark[stiva][j])
                            {
                                C[stiva][ nr[stiva] ] = C[stiva][ nr[stiva]-1 ]+(A[i][j]+1)&1;
                                Mark[stiva][j] = 1;
                                St[stiva][ nr[stiva]++ ] = j;
                            }
                        if (nr[stiva]==N)
                        {
                                if (min>C[stiva][N-1])
                                {
                                   min = C[stiva][N-1];
                                   for (j = nsol = 0; j < N; j++)
                                       Sol[nsol++] = St[stiva][j];
                                }
                        }
                    }
        }

        printf("%d\n", min);
        for (i = 0; i < nsol-1; i++)
        {
            if ((A[ Sol[i] ][ Sol[i+1] ]+A[ Sol[i+1] ][ Sol[i] ])==0)
               printf("%d %d\n", Sol[i], Sol[i+1]);
            else
                if (A[ Sol[i+1] ][ Sol[i] ]==1)
                   j = Sol[i], Sol[i] = Sol[i+1], Sol[i+1] = j;
        }
        for (i = 0; i < nsol; i++) printf("%d ", Sol[i]);
        printf("\n");
}

void back(int nv)
{
        int i, j, ev, x;

        if (nv==N)
        {
                for (i = x = 0; i < nv-1; i++)
                    if (!A[ V[i] ][ V[i+1] ]) x++;
                if (x<min)
                {
                        min = x;
                        for (j = nsol = 0; j < nv; j++)
                            Sol[nsol++] = V[j];
                }
        }

        for (i = 1; i <= N; i++)
        {
                for (j = 0, ev = 1; ev && j < nv; j++)
                    if (V[j]==i) ev = 0;
                if (ev)
                {
                        V[nv] = i;
                        back(nv+1);
                }
        }
}

int main()
{
        int i, j, k;

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

        scanf("%d%d", &N, &M);

        for (k = 0; k < M; k++)
        {
            scanf("%d%d", &i, &j);
            A[i][j] = 1;
        }

        if (N>10) greedy();
        else {
             back(0);
             printf("%d\n", min);
             for (i = 0; i < nsol-1; i++)
                 if (!A[ Sol[i] ][ Sol[i+1] ]) printf("%d %d\n", Sol[i], Sol[i+1]);
             for (i = 0; i < nsol; i++) printf("%d ", Sol[i]);
             printf("\n");
             }

        return 0;
        
}