3410 - 【模板】二分图最大匹配

题目描述

给定一个二分图,其左部点的个数为 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。

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

题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 1
通过人数 1
金币数量 4 枚
难度 未标记


上一题 下一题