题目描述

给定一个二分图，其左部点的个数为 n，右部点的个数为 m，边数为 e，求其最大匹配的边数。

左部点从 1 至 n 编号，右部点从 1 至 m 编号。

输入格式

输入的第一行是三个整数，分别代表 n，m 和 e。

接下来 e 行，每行两个整数 u, v，表示存在一条连接左部点 u 和右部点 v 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

样例

1 1 1 
1 1

1

4 2 7 
3 1 
1 2 
3 2 
1 1 
4 2 
4 1 
1 1

2

提示

对于全部的测试点，保证：

1≤n,m≤500。

1≤e≤5×10^4。

1≤u≤n，1≤v≤m。

不保证给出的图没有重边。

原题地址：https://www.luogu.com.cn/problem/P3386

By QLU_钟志强