#include<fstream>
#include<queue>
#include<vector>
#include<cstring>
#define DIM 300
using namespace std;
ifstream fin("strazi.in");
ofstream fout("strazi.out");
int L[DIM], R[DIM], n, m, x, y, f[DIM], s[DIM], poz;
vector<int> v[DIM];
vector< pair<int,int> > sol;
queue<int> q;
int cupleaza( int nod ){
    if( f[nod] == 1 ){
        return 0;
    }
    f[nod] = 1;
    for( int i = 0; i < v[nod].size(); i++ ){
        int vecin = v[nod][i];
        if( R[vecin] == 0 ){
            L[nod] = vecin;
            R[vecin] = nod;
            return 1;
        }
    }
    for( int i = 0; i < v[nod].size(); i++ ){
        int vecin = v[nod][i];
        if( cupleaza( R[vecin] ) == 1 ){
            L[nod] = vecin;
            R[vecin] = nod;
            return 1;
        }
    }
    return 0;
}
int main(){
    fin >> n >> m;
    for( int i = 1; i <= m; i++ ){
        fin >> x >> y;
        v[x].push_back(y);
    }
    int ok = 1;
    while( ok == 1 ){
        ok = 0;
        memset( f, 0, sizeof(f) );
        for( int i = 1; i <= n; i++ ){
            if( L[i] == 0 && cupleaza( i ) == 1 )
                ok = 1;
        }
    }
    for( int i = 1; i <= n; i++ ){
        if( R[i] == 0 )
            q.push(i);
    }
    poz = 0;
    while( !q.empty() ){
        int nod = q.front();
        s[++poz] = nod;
        while( L[nod] != 0 ){
            s[++poz] = L[nod];
            nod = L[nod];
        }
        q.pop();
        if( !q.empty() )
            sol.push_back( make_pair( nod, q.front() ) );
    }
    fout << sol.size() << "\n";
    for( int i = 0; i < sol.size(); i++ ){
        fout << sol[i].first << " " << sol[i].second << "\n";
    }
    for( int i = 1; i <= n; i++ ){
        fout << s[i] << " ";
    }
    return 0;
}