Responsive image

问题 I: 星团

问题 I: 星团

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

有两个星团，分别叫做星团A和星团B。星团A中有n颗星星（编号为1, 2, 3, ..., n），星团B中也有m颗星星（编号为1, 2, 3, ..., m）。星星们感到孤单，想要找到属于自己的伙伴，但只能选择来自另一个星团的星星作为伙伴（星团A的星星只能选择星团B的星星，反之亦然）。
现在有k根红线，每根红线连接了星团A和星团B中的一对星星。每颗星星可以通过红线与多颗星星相连，但每颗星星最终只能选择一个伙伴，并且这个伙伴必须是通过红线连接的。
你的任务是根据这些红线的连接情况，尽可能为星星们配对伙伴。请问最多可以配对出多少对伙伴？

输入描述

第一行n，m，k分别代表a星团数量，b星团数量和k根红线
接下来k行每行有两个整数u，v。代表a星团中编号为u的星星与b星团中编号为v的星星有红线连接

输出描述

一个整数，代表可以最大结成几对伙伴

样例输入

2 2 4
1 1
1 2
2 1
2 2

样例输出

2

提示


[提交][状态]
ACM算法攻关部