#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;

#define MAXN 525
#define mp make_pair
#define pb push_back
#define PII pair<int, int>

int N, M, src, dest;
int G[MAXN][MAXN], C[MAXN][MAXN], Q[MAXN], from[MAXN], viz[MAXN];
vector< PII > sol;
int K, drum[MAXN];

int bfs(void)
{
    int inc, sf, x, i, ok = 1;

    memset(viz, 0, sizeof(viz));
    Q[inc = sf = 0] = src, viz[src] = 1, from[src] = -1;

    while(inc <= sf && ok)
    {
        for(x = Q[inc++], i = src; i <= dest; i++)
         if(C[x][i] > 0 && !viz[i])
         {
            from[i] = x, viz[i] = 1, Q[++sf] = i;
            if(i == dest) { x = dest, ok = 0; break ; }
         }
    }

    if(x != dest) return 0;

    while(from[x] > -1) C[from[x]][x]--, C[x][from[x]]++, x = from[x];

    return 1;
}

void dfs(int x)
{
    int i;
    for(drum[++K] = x, i = 1; i <= N; i++)
     if(C[x][N+i] == 0 && G[x][N+i])
        dfs(i);
}

void solve(void)
{
    int i, j, k, x, y, fl = 0, last;

    while( bfs() ) fl++;

    for(last = -1, i = 1; i <= N; i++)
     if(C[N+i][dest] == 1)
     {
        if(last != -1) sol.pb( mp(last, i) );
        dfs(i), last = drum[K];
     }    
}

void read_data(void)
{
    int i, j, k;

    scanf("%d %d\n", &N, &M), src = 0, dest = 2*N+1;

    for(i = 1; i <= M; i++)
    {
        scanf("%d %d\n", &j, &k);
        if(j != k) G[j][k+N] = 1, C[j][k+N] = 1;
    }
    
    for(i = 1; i <= N; i++) C[src][i] = C[i+N][dest] = 1;
}

void write_data(void)
{
    int i;

    printf("%d\n", sol.size());
    for(i = 0; i < sol.size(); i++)
        printf("%d %d\n", sol[i].first, sol[i].second);
    for(i = 1; i <= N; i++) printf("%d ", drum[i]);
}

int main(void)
{
    freopen("strazi.in", "rt", stdin);
    freopen("strazi.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}