HC Karp

/* Hopcroft-Karp max maching */
/* O( sqrt(V)*E ) */
/* Spoj 4206. Fast Maximum Matching */

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
#define MAX 100007
#define INF 7777777

vector<long> Edge[MAX+7];
long L,R,n,m;   // L->left vertex ; R->Right vertex ; n->Tot vertex(L+R)
long D[MAX+7];  // D->Shortest distance
long M[MAX+7];
/* Node 0 is used as dummy here */
bool Bfs( void )
{
    queue<long> q;
    long i;
    for( i=1;i<=L;i++){
        if( M[i] ) D[i] = INF;
        else{
            D[i] = 0;
            q.push( i );
        }
    }
    D[0] = INF;
    while( !q.empty()){
        long u = q.front();
        q.pop();
        for( i=0;i<Edge[u].size();i++){
            long v = Edge[u][i];
            if( D[M[v]] == INF ){
                D[M[v]] = D[u] + 1;
                q.push( M[v] );
            }
        }
    }
    return D[0] != INF;
}
bool Dfs( long u )
{
    if( !u ) return true;
    long i;
    for( i=0;i<Edge[u].size();i++){
        long v = Edge[u][i];
        if( D[M[v]]==D[u]+1 && Dfs( M[v] )){
            M[u] = v;
            M[v] = u;
            return true;
        }
    }
    D[u] = INF;
    return false;
}
int main( void )
{
    long i,j,u,v;
    //freopen("text1.txt","r",stdin );
    scanf("%ld%ld%ld",&L,&R,&m );
    n = L+R;
    for( i=1;i<=m;i++){
        scanf("%ld%ld",&u,&v );
        Edge[u].push_back( L+v );
        Edge[L+v].push_back( u );
    }
    long Ans = 0;
    while( Bfs()){
        for( i=1;i<=L;i++){
            if( M[i] ) continue;
            if( Dfs( i )){
                Ans++;
            }
        }
    }
    printf("%ld\n",Ans );
    return 0;
}