#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
using namespace std;

#define DIM 20001

int N, M, XXX, L[ DIM ], R[ DIM ];
bitset <DIM> F;
queue <int> Q;
vector <int> V[ DIM ];

inline void df( const int &X ) {

    if( !X )
        return;

    printf( "%d ", X );
    df( L[ X ] );
}

inline int pairup( const int &X ) {

    unsigned int I;

    if( F[ X ] )
        return 0;

    F[ X ] = 1;
    for( I = 0; I < V[ X ].size(); ++I )
        if( !R[ V[ X ][ I ] ] ) {

            L[ X ] = V[ X ][ I ];
            R[ V[ X ][ I ] ] = X;

            return 1;
        }

    for( I = 0; I < V[ X ].size(); ++I )
        if( pairup( R[ V[ X ][ I ] ] ) ) {

            L[ X ] = V[ X ][ I ];
            R[ V[ X ][ I ] ] = X;

            return 1;
        }

    return 0;
}

int main() {

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

    int i, x, y, ok;

    scanf( "%d %d", &N, &M );
    for( i = 0; i < M; ++i ) {

        scanf( "%d %d", &x, &y );
        V[ x ].push_back( y );
    }

    do {

        ok = 0;
        F.reset();
        for( i = 1; i <= N; ++i )
            if( !L[ i ] && pairup( i ) )
                ok = 1;
    }
    while( ok );

//    for( int i = 1; i <= N; ++i )
//        printf( "%d %d\n", L[ i ], R[ i ] );

    for( i = 1; i <= N; ++i )
        if( !L[ i ] )
            ++XXX;
    for( i = 1; i <= N; ++i )
        if( !R[ i ] )
            Q.push( i );

    printf( "%d\n", --XXX );
    for( i = 1; i <= N && L[ i ]; ++i );
    for( ++i; i <= N; ++i )
        if( !L[ i ] ) {

            printf( "%d %d\n", i, Q.front() );
            L[ i ] = Q.front();
            R[ Q.front() ] = i;
            Q.pop();
        }
    for( i = 1; i <= N; ++i )
        if( !R[ i ] ) {

            df( i );
            break;
        }

    return 0;
}