B. 【模板】二分图最大匹配

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

题目来源于洛谷 P3386 ,其数据难度更强

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

左部点从 1 n 编号,右部点从 1 m 编号。

输入格式

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

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

输出格式

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

样例

输入样例

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