861. 二分图的最大匹配

给定一个二分图,其中左半部包含$n_1$个点(编号1~$n_1$),右半部包含$n_2$个点(编号1~$n_2$),二分图共包含m条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配:给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。

输入格式

第一行包含三个整数 $n_1$、 $n_2$ 和 $m$。

接下来m行,每行包含两个整数u和v,表示左半部点集中的点u和右半部点集中的点v之间存在一条边。

输出格式

输出一个整数,表示二分图的最大匹配数。

数据范围

$1 \le n_1,n_2 \le 500$,
$1 \le u \le n_1$,
$1 \le v \le n_2$,
$1 \le m \le 10^5$

输入样例:

2 2 4
1 1
1 2
2 1
2 2

输出样例:

2