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

using namespace std;

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

#define NMAX 20

inline long long ultim(long long x)
{
    return (long long)x%10;
}

inline long long penultim(long long x)
{
    return (long long)((long long)x/10)%10;
}

int n, m;
short nrmin = 100;
long long confmin;
set<short> a[NMAX];
short uz[NMAX];

void read()
{
    scanf("%d %d", &n, &m);
    for(int i = 0, x, y; i < m; ++i)
        scanf("%d %d", &x, &y), a[x].insert(y);
}

void back(long long crt, int nr)
{
    if(nr == n)
    {
        short solcrt = 0;
        long long aux = crt;
        while(aux > 9)
        {
            if(a[ penultim(aux) ].find( ultim(aux) ) == a[ penultim(aux) ].end())
                ++solcrt;
            aux /= 10;
        }
        if(solcrt < nrmin)
            nrmin = solcrt, confmin = crt;
    }
    else
        for(short i = 1; i <= n; ++i)
            if(!uz[i])
            {
                ++uz[i];
                back(crt*10 + i, nr+1);
                --uz[i];
            }
}

int main()
{
    freopen("strazi.in", "r", stdin);
    freopen("strazi.out", "w", stdout);
    
    read();
    
    if(n > 18)
    {
        printf("0\n");
        for(short i = 1; i <= n; ++i) printf("%d ", i);
        return 0;
    }
    for(short i = 1; i <= n; ++i)
        ++uz[i], back(i, 1);
    
    vector< pair<int, int> > v;
    long long aux = confmin;
    printf("%d\n", nrmin);

    while(aux > 9)
    {
        if(a[ penultim(aux) ].find( ultim(aux) ) == a[ penultim(aux) ].end())
            v.pb( MP(penultim(aux), ultim(aux)) );
        aux /= 10;
    }
    for(vector< pair<int, int> > :: iterator it = v.begin(); it != v.end(); ++it)
        printf("%d %d\n", (*it).ff, (*it).ss);

    vector<int> z;
    while(confmin)
    {
        z.pb( ultim(confmin) );
        confmin /= 10;
    }
    for(int i = z.sz-1; i >= 0; --i)
        printf("%d ", z[i]);
    
    return 0;
}