1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #define maxn 2008 5 #define maxm 10008 6  7 struct edge{ 8     int u,v,next; 9 }eg[maxm];10 11 int n,m,sum;12 int last[maxn],l[maxn];13 bool pd[maxn];14 15 void add(int u,int v)16 {17     eg[++sum].u=u;18     eg[sum].v=v;19     eg[sum].next=last[u];20     last[u]=sum;21 }22 bool find(int u)23 {24     for (int i=last[u];i;i=eg[i].next)25     {26         int v=eg[i].v;27         if (!pd[v])28         {29             pd[v]=true;30             if ( (!l[v]) || find(l[v]) )31             {32                 l[v]=u;33                 return true;34             }35             36         }37     }38     return false;39 }40 int main()41 {42     scanf("%d%d",&n,&m);43     int i,j,sum=0,ans=0;44     for(i=1;i<=m;i++)45     {46         scanf("%d",&j);47         add(i,j);48         scanf("%d",&j);49         add(i,j);50     }51     52     memset(l,0,sizeof(l));53     for (i=1;i<=m;i++)54     {55         memset(pd,0,sizeof(pd));56         if (find(i)) ans++; else break; 57     }58     printf("%d",ans);59 }