#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <cmath>

using namespace std;

const int maxn = 3010;

const int INF = 1<<28;

int dx[maxn], dy[maxn];

int cx[maxn], cy[maxn];

vector <int> G[maxn];

int dis;

int n, m;

bool vis[maxn];

bool search()

{

	queue <int> 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;

}