#include <cstdio>
#include <cstring>

#define NMAX 256
#define INF 0x3f3f3f3f

int N, M;
int d[NMAX][1<<12], pred[NMAX][1<<12];
int a[NMAX][NMAX];

void read ()
{
    scanf ("%d %d\n", &N, &M);
    
    int i, x, y; 
    for (i = 0; i < M; ++ i)
    {
        scanf ("%d %d\n", &x, &y);
        a[x][y] = 1;
    }    
}

int Get_Min (int i, int mask)
{
    if (d[i][mask] < INF)
        return d[i][mask];
    
    int j, tmp, MIN = INF, p = 0;
    
    //printf ("%d   %d\n", i, mask);
    for (j = 1; j < mask; j <<= 1);
    if (mask == j)
    {
        d[i][mask] = 0;
        return 0;
    }
    
    for (j = 1; j <= N; ++ j)
        if (mask & (1<<(j-1)) && i != j)
        {
            tmp = Get_Min (j, mask - (1<<(i-1)));
            if (!a[j][i])
                ++ tmp;
                
            if (MIN > tmp)
            {
                p = j;
                MIN = tmp;
            }
        }
    
    d[i][mask] = MIN;
    pred[i][mask] = p;
    return MIN;
}

void constr (int i, int mask)
{
    if (!mask)
    {
        if (d[i][mask] == d[pred[i][mask]][mask-(1<<(i-1))] + 1)
            printf ("%d %d\n", pred[i][mask], i);
        return;
    }
    constr (pred[i][mask], mask - (1<<(i-1)));
    if (d[i][mask] == d[pred[i][mask]][mask-(1<<(i-1))] + 1)
        printf ("%d %d\n", pred[i][mask], i);
}

void reconst (int i, int mask)
{
    if (!mask)
        return;
    reconst (pred[i][mask], mask - (1<<(i-1)));
    printf ("%d ", i);
}

void solve ()
{
    int MIN, sol = 256, nod, i;
    
    memset (d, INF, sizeof (d));
    
    for (i = 1; i <= N; ++ i)
    {
        MIN = Get_Min (i, ((1<<N) - 1));
        //printf ("%d\n", MIN);
        if (MIN <= sol)
        {
            sol = MIN;
            nod = i;
        }
    }    
    
    printf ("%d\n", sol);
    
    constr (nod, ((1<<N)-1));
    reconst (nod, ((1<<N)-1));
    
    printf ("\n");
}

int
 main ()
{
    freopen ("strazi.in", "rt", stdin);
    freopen ("strazi.out", "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}