#include <iostream>
#include <vector>
using namespace std;

int N, M, R[256], L[256], U[256], nr;
vector<int> G[256], D[256];

int pairUp(int nod) {
    if(U[nod]) return 0;
    U[nod]=1;
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(!R[(*it)]) {
              L[nod]=(*it);
              R[(*it)]=nod;
              return 1;
         }
    }
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(pairUp(R[(*it)])) {
              L[nod]=(*it);
              R[(*it)]=nod;
              return 1;
         }
    }
    return 0;
}

int main() {
    FILE *f1=fopen("strazi.in", "r"), *f2=fopen("strazi.out", "w");
    int i, j, p, q, ok=1;
    fscanf(f1, "%d%d", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d%d", &p, &q);
         G[p].push_back(q);
    }
    while(ok) {
         memset(U, 0, sizeof(U));
         ok=0;
         for(i=1; i<=N; i++) {
              if(!L[i]) {
                   if(pairUp(i)) { ok=1; }
              }
         }
    }
    for(i=1; i<=N; i++) {
         if(!L[i]) {
              nr++;
              j=i;
              while(j) {
                   D[nr].push_back(j);
                   j=R[j];
              }
         }
    }
    fprintf(f2, "%d\n", nr-1);
    for(i=1; i<=nr-1; i++) {
         fprintf(f2, "%d %d\n", D[i].back(), D[i+1].front());
    }
    for(i=1; i<=nr; i++) {
         for(vector<int>::iterator it=D[i].begin(); it!=D[i].end(); it++) {
              fprintf(f2, "%d ", (*it));
         }
    }
    fclose(f1); fclose(f2);
    return 0;
}