/*

这个问题将是每行一个x作为节点x,没有列y作为节点y,障碍物的坐标xy来自x至y的

边缘。图建的问题后，变成，拿得最少的点，因此，所有这些点与相邻边缘，即最小

点覆盖，与匈牙利算法来解决。

-------------------------------

定理：最小点覆盖数 = 最大匹配数。即求图的最大匹配就可以，匈牙利算法

-------------------------------

模板解说：

bool find(int v)

{

    for(int i=1; i<=n; i++)

    {

        if(g[v][i] && !vis[i])假设结点i和v相邻而且未被查找过

        {

            vis[i] = true;标记结点i为已查找过

            if(link[i] == 0 || find(link[i]))link[i] == 0表示i不再前一个匹配M中||i在匹配M中，可是从与i相邻的节点出发能够有增广路

            {

                link[i] = v;记录查找成功记录

                return true;返回查找成功

            }

        }

    }

    return false;

}

-------------------------------

匈牙利算法介绍：

匈牙利算法是由匈牙利数学家Edmonds于1965年提出。因而得名。

匈牙利算法是基于

Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找

增广路径。它是一种用增广路径求二分图最大匹配的算法。

---------------------------------

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n,k,r,c;

int g[550][550];

bool vis[10010];

int link[10010];

bool find(int v)

{

    for(int i=1; i<=n; i++)

    {

        if(g[v][i] && !vis[i])

        {

            vis[i] = true;

            if(link[i] == 0 || find(link[i]))

            {

                link[i] = v;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    //freopen("input.txt","r",stdin);

    int ans;

    while(scanf("%d%d",&n,&k) != EOF)

    {

        memset(g,0,sizeof(g));

        memset(link,0,sizeof(link));

        for(int i = 0; i < k; i++)

        {

            scanf("%d%d",&r,&c);

            g[r][c] = 1;

        }

        ans = 0;

        for(int i=1; i<=n; i++)

        {

            memset(vis,0,sizeof(vis));//清空上次搜索时的标记

            if(find(i))//从节点i尝试扩展

                ans++;

        }

        printf("%d\n",ans);

    }

    return 0;

}

---------------------------------------------------------------------

战斗，不留情面。斗争。永不停歇~~~~~~~~~~