#include <bits/stdc++.h>
#define maxN 260
using namespace std;
bool seen[maxN];
vector<int> path;
vector<int> v[maxN];
int _left[maxN],_right[maxN];
bool edges[maxN][maxN];
int n,m,i,j,x,y;
bool pairup(int nod)
{
if(seen[nod])
return false;
seen[nod]=true;
for(auto it:v[nod])
if(!_right[it])
{
_right[it]=nod;
_left[nod]=it;
return true;
}
for(auto it:v[nod])
if(pairup(_right[it]))
{
_right[it]=nod;
_left[nod]=it;
return true;
}
return false;
}
void createPath(int nod)
{
path.push_back(nod);
if(_left[nod])
createPath(_left[nod]);
}
int main()
{
freopen("strazi.in","r",stdin);
freopen("strazi.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
edges[x][y]=true;
v[x].push_back(y);
}
bool ok=true;
int maxmatch=0;
while(ok)
{
ok=false;
memset(seen,false,sizeof(seen));
for(i=1;i<=n;i++)
if(!_left[i])
ok|=pairup(i);
}
for(i=1;i<=n;i++)
if(_left[i])
maxmatch++;
printf("%d\n",n-1-maxmatch);
for(i=1;i<=n;i++)
if(!_right[i])
createPath(i);
for(i=0;i<path.size()-1;i++)
if(!edges[path[i]][path[i+1]])
printf("%d %d\n",path[i],path[i+1]);
for(auto it:path)
printf("%d ",it);
return 0;
}