#include <bits/stdc++.h>
using namespace std;

fstream in ( "strazi.in" , ios::in  );
fstream out( "strazi.out", ios::out );

const int DIM = 3e2 + 5;

int lef[DIM], rig[DIM];

bitset<DIM> oki, mrk[DIM];
vector<int> edg[DIM], lst; vector<pair<int, int>> ans;

bool slv( int x ) {
    if( oki[x] == true )
        return false;
    oki[x] = true;
    
    for( int y : edg[x] ) {
        if( rig[y] == 0 ) {
            lef[x] = y;
            rig[y] = x;
            
            return true;
        }
    }
    
    for( int y : edg[x] ) {
        if( slv( rig[y] ) == true ) {
            lef[x] = y;
            rig[y] = x;
            
            return true;
        }
    }
    
    return false;
}

void dfs( int x ) {
    lst.push_back( x );
    
    if( lef[x] != 0 )
        dfs( lef[x] );
    
    return;
}

int main( void ) {
    
    int n, m;
    in >> n >> m;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y;
        in >> x >> y;
        
        edg[x].push_back( y );
        mrk[x][y] = true;
    }
    
    bool ok;
    do {
        ok = true; oki.reset();
        for( int i = 1; i <= n; i ++ ) {
            if( lef[i] == 0 && slv( i ) == true )
                ok = false;
        }
    } while( ok == true );
    
    for( int i = 1; i <= n; i ++ ) {
        if( rig[i] == 0 )
            dfs( i );
    }
    
    for( int i = 1; i < lst.size(); i ++ ) {
        if( mrk[lst[i - 1]][lst[i]] == false )
            ans.push_back( make_pair( lst[i - 1], lst[i] ) );
    }
    
    out << ans.size() << "\n";
    for( pair<int, int> pr : ans )
        out << pr.first << " " << pr.second << "\n";
    for( int x : lst )
        out << x << " ";
    out << "\n";
    
    return 0;
}