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

#define Nmax 256

int N, M;
vector<int> G[Nmax];
int U[Nmax], st[Nmax], dr[Nmax], nr;

void citire()
{
 int i, x, y;
 
 freopen("strazi.in","r",stdin);
 scanf("%d %d", &N, &M);
 for (i=0; i<N; ++i)
     {
      scanf("%d %d", &x, &y);
      G[x].push_back(y);
     } 
}

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

void hopcroft()
{
 int gasit, i;
 
 gasit = 1;
 while (gasit)
       {
        gasit = 0;
        memset(U, 0, sizeof(U));
        for (i=1; i<=N; ++i)
            if (!dr[i])
               if (cupleaza(i))
                  {
                   ++nr;
                   gasit = 1;                        
                  }                     
       }
}

void solutie()
{
 int i, nod, gasit, first;
 
 memset(U, 0, sizeof(U));
 for (i=1; i<=N; ++i)
     if (!st[i]) break;
 gasit = 1;
 U[i] = dr[i];
 first = i;
 
 while (gasit)
       {
        gasit = 0;
        nod = i;
        while (dr[nod])
              {
               nod=dr[nod];
               U[nod] = dr[nod];
              }
        for (i=1; i<=N; ++i)
            if (!st[i] && !U[i] && i!=nod) 
                          { printf("%d %d\n",nod,i);
                            U[nod] = i;
                            gasit=1;
                            break; }
        nod = i;
       }

 printf("%d ",first);
 while (U[first])
       {
        first = U[first];
        printf("%d ",first);
       }
 printf("\n");      
}

int main()
{
 citire();
 
 hopcroft();
 
 freopen("strazi.out","w",stdout);
 printf("%d\n", N-nr-1);
 solutie();
 fclose(stdout);
 
 return 0;
}