using namespace std;

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <iostream>

#include <cassert>

#define NDEBUG

#define FIN "felinare.in"
#define FOUT "felinare.out"

#define maxn 8192


#ifndef NDEBUG
int stp;
#endif



vector<vector<short> > x;

char aa[maxn+2000][(maxn/8) +2000];

int n, m, E;
short source, sink;
short t[maxn<<1];
short d[maxn<<1];
bool Viz[maxn<<1];
int bfs();
void solve();

void read()
{

	int i,p, q;
		scanf("%d %d\n", &n, &m);
	//	a.clear();
	//	x.clear();
		
	//	a.resize(n+n+2);
	//	for(i=0;i<n+n+2;i++) a[i].resize(n+n+2);
		source=0;
		sink=n+n+1;
		x.resize(n+n+2);
		for(i=0;i<m;++i)
		{
			scanf("%d %d\n", &p, &q);
	//		a[p][q+n]=1;
			aa[p][(q+n)>>3]|=(1<<((q+n)&7));
			x[p].push_back(q+n);
			x[q+n].push_back(p);
			
		}
		for(i=1;i<=n;++i)aa[source][i>>3]|=(1<<(i&7)), x[source].push_back(i), x[i].push_back(source);
		for(i=n+1;i<sink;++i) aa[i][sink>>3]|=(1<<(sink&7)), x[i].push_back(sink), x[sink].push_back(i);
		
		

		
}


int bfs()
{
	short Q[maxn<<1], p=1, q=1;
	bool viz[maxn<<1];
	memset(viz, 0,sizeof(viz));
	//memset(t, -1, sizeof(t));
	memset(d, 0, sizeof(d));
	viz[source]=1;
	Q[1]=source;
	d[1]=0;
	int u;
	short i;
	vector<short>::iterator it, xu;
	
	while(p<=q)
	{
		u=Q[p++];
		xu=x[u].end();
		for(it=x[u].begin();it!=xu;++it)
		{
		  i=*it;
		  if(!viz[i] && (aa[u][(i)>>3]&(1<<((i)&7))))
			{
				viz[i]=1;
				d[i]=d[u]+1;
				t[i]=u;
				Q[++q]=i;
			}
		}
	}
	
	if(d[sink]==0) return 0;
	return 1;
}



int flow, ok=1, dsink,nr;


void dfs2(short nd, short nr)
{

  printf("%d %d\n",nd, nr);
	if(nr>sink) return;

	if(nd==sink) { ++flow; ok=0; return;}
	if(nd==source) ok=1;

	Viz[nd]=1;

	vector<short>::iterator it, xnd;
	short i;
	xnd=x[nd].end();
	for(it=x[nd].begin(); it!=xnd; ++it)
	{
	   i=*it;
		if(ok &&  !Viz[i]  && (  aa[nd][(i)>>3]&(1<<((i)&7 ))))
		 {
			//++nr;
			dfs2(i, nr+1);
			//--nr;
			if(!ok)
			{
				aa[nd][(i)>>3]&=~(1<<((i)&7));
				aa[i][nd>>3]|=(1<<(nd&7));
				break;
			}
		}
	}
}
	


void solve()
{
	int i, j;
	int p;
	
	flow=0;
	vector<short>::iterator it;
	while(bfs())
	{
		
	  	memset(Viz, 0, sizeof(bool)*(sink+2));
		//for(i=source;i<=sink;++i) Viz[i]=0;
		ok=1;
		nr=0;
		dsink=d[sink];	
		dfs2(source, 0);



	}
	printf("%d\n", 2*n-flow);
	
}






int main()
{
	freopen(FIN, "r", stdin);
       	freopen(FOUT, "w", stdout);

	read();
	solve();
	
	return 0;
}