# include <cstdio>
# include <vector>

using namespace std;

# define FIN "strazi.in"
# define FOUT "strazi.out"
# define MAX_N 256

int N, M, i;
int s[MAX_N];
vector <int> G[MAX_N];
int L[MAX_N], R[MAX_N];

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

       void cuplaj() {
           int ok = 1;
           
           while (ok) {
                 ok = 0;
                 memset(s, 0, sizeof(s));
                 for (int i = 1; i <= N; ++i)
                    if (!L[i])
                       if (PairUp(i)) ok = 1;
           }
       }
       
       int df(int Nod) {
           while (L[Nod]) Nod = L[Nod];
           return Nod;
       }

       int main() {
           freopen(FIN, "r", stdin);
           freopen(FOUT, "w", stdout);
           
           scanf("%d%d", &N, &M);
           
           int x, y;
           for (i = 1; i <= M; ++i) {
               scanf("%d%d\n", &x, &y);
               
               G[x].push_back(y);
           }
           
           cuplaj();
           
           int ct = 0, prev = 0, cur;
           for (i = 1; i <= N; ++i)
              if (!L[i]) ++ct;
              
           printf("%d\n", ct - 1);
           
           for (i = 1; i <= N; ++i)
              if (!R[i]) {
                 if (prev) {
                    G[prev].push_back(i);
                    L[prev] = i;
                    R[i] = prev;
                    printf("%d %d\n", prev, i);
                 }
                 prev = df(i);
              }
           
           for (i = 1; i <= M; ++i)
              if (!R[i]) {
                  while (L[i]) {
                      printf("%d ", i);
                      i = L[i];
                  }
                  printf("%d", i);
              }
           
           return 0;
       }