#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #define min(a,b) (a)>(b)?(b):(a) #define max(a,b) (a)>(b)?(a):(b) #define inf 99999999 using namespace std; int cnt; int source,N; int sink,ans; int c[4400]; int H[20410]; int d[4410]; struct egde { int u,v,c,next; }; egde a[20000]; void init() { int i; for(i=0;i<24000;i++) H[i]=-1; cnt=0; } void add(int u,int v,int c) { a[cnt].v=v; a[cnt].c=c; a[cnt].next=H[u]; H[u]=cnt++; } void build(int u,int v,int c) { add(u,v,c); add(v,u,0); } int dfs(int u,int flow) { if(u==sink) return flow; int tt,res=0,delta; for(tt=H[u];~tt;tt=a[tt].next) { int &v=a[tt].v,&c=a[tt].c; if(c&&d[u]==d[v]+1){ delta=dfs(v,min(flow,c)); c-=delta; a[tt^1].c+=delta; res+=delta; flow-=delta; if (!flow) return res; } } if(!res) { if(!--c[d[u]]) d[source]=N+1; ++c[++d[u]]; } return res; } void sap() { memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); c[source]=N; while(d[source]<N) ans+=dfs(source,inf); } int main() { int n,k,i,x,y; while(~scanf("%d%d",&n,&k)) { init(); source=0; sink=n*2+1; N=sink+1; ans=0; for(i=1;i<=k;i++) { scanf("%d%d",&x,&y); build(x,y+n,inf); } for(i=1;i<=n;i++) { build(source,i,1); build(i+n,sink,1); } sap(); printf("%d\n",ans); } return 0; }