1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 using namespace std; 5 vector<int>G[2002]; 6 typedef vector<int>::iterator ITER; 7 int n,m,mat[2002],x,y; 8 bool vis[2002]; 9 bool dfs(int U)10 {11     for(ITER it=G[U].begin();it!=G[U].end();it++)12       if(!vis[*it])13         {14           vis[*it]=1;15           if(mat[*it]==-1||dfs(mat[*it]))16             {17               mat[*it]=U;18               return 1;19             }20         }21     return 0;22 }23 int max_match()24 {25     memset(mat,-1,sizeof(mat)); int res=0;26     for(int i=1;i<=n;i++)27       {28         memset(vis,0,sizeof(vis));29         if(dfs(i)) res++;30         else return res;31       } return res;32 }33 int main()34 {35     scanf("%d%d",&m,&n);36     for(int i=1;i<=n;i++)37       {38         scanf("%d%d",&x,&y);39         G[i].push_back(x+1+n);40         G[x+1+n].push_back(i);41         G[i].push_back(y+1+n);42         G[y+1+n].push_back(i);43       } printf("%d\n",max_match());44     return 0;45 }