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