#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn = 3010;const int INF = 1<<28;int dx[maxn], dy[maxn];int cx[maxn], cy[maxn];vector 
           
             G[maxn];int dis;int n, m;bool vis[maxn];bool search(){ queue 
            
              Q; int dis = INF; memset(dx, -1, sizeof(dx)); memset(dy, -1, sizeof(dy)); for(int i = 0; i < n; i++) if(cx[i] == -1) { Q.push(i); dx[i] = 0; } while(!Q.empty()) { int u = Q.front(); Q.pop(); if(dx[u] > dis) break; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(dy[v] == -1) { dy[v] = dx[u] + 1; if(cy[v] == -1) dis = dy[v]; else { dx[cy[v]] = dy[v] + 1; Q.push(cy[v]); } } } } return dis != INF;}bool dfs(int u){ for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(vis[v]) continue; vis[v] = true; if(dy[v] == dx[u]+1) { if(cy[v] != -1 && dy[v] == dis) continue; if(cy[v] == -1 || dfs(cy[v])) { cy[v] = u; cx[u] = v; return true; } } } return false;}int match(){ int ans = 0; memset(cx, -1, sizeof(cx)); memset(cy, -1, sizeof(cy)); while(search()) { memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++) if(cx[i] == -1 && dfs(i)) ans++; } return ans;}