调度机器

骑士驱逐完了，但Zero的工厂里还有机器——需要调度。

"调度？"CC问。

"对。"你说，"$n$个机器，$m$个任务。每个机器能做某些任务，每个任务需要一个机器。求最多能完成多少任务。"

"机器？"

"对。"你说，"二分图——左边是机器，右边是任务。边表示机器能做这个任务。"

"二分图？"

"对。"你说，"点分成两边，边只在两边之间，不在同一边。"

"最多？"

"对。"你说，"最大匹配——选最多的边，没有公共点。"

"咋算？"

"匈牙利算法。"你说，"从一个机器出发，找能匹配的任务；如果任务已被占，看能不能给原主人找另一个。"

"抢？"

"对。"你说，"像抢座位——你坐了我的，我就找另一个。"

"第47个机器。"你说，"如果能做任务A和B，看A和B哪个更好。"

"哪个好？"

"看整体。"你说，"选A能让其他机器更灵活，就选A。"

"灵活？"

"对。"你说，"匹配的本质是让资源灵活流动——每台机器找到最适合的任务。"

"像分工？"

"对。"你说，"像分工——每个人做自己擅长的，整体效率最高。"

"如果不会做？"

"不分配。"你说，"不能强塞——不会做硬做，做不好。"

"空着？"

"对。"你说，"有些机器可能空着——任务不够。"

"有些任务？"

"也空着。"你说，"没有机器能做，或者机器不够。"

"那咋办？"

"扩大匹配。"你说，"加机器，或者加任务。"

"加不了？"

"接受现实。"你说，"最大匹配就是极限。"

CC看着那些机器和任务——像供需，像配对，像某种必须匹配的东西。

"匹配？"她问。

"对。"你说，"找到最合适的搭档。"

"我们匹配？"

"对。"你说，"我们三个，互相匹配——缺一个都不行。"

Echo把匹配过程投射出来——一条一条边连上，像红线，像缘分。

"以前我是单着的。"她说，"现在……匹配了。"

"因为我们在。"CC说。

"对。"Echo说，"因为你们在。

题目描述

$n$个机器，$m$个任务。每个机器能做某些任务。求最大匹配数。

输入格式

第一行$n,m$和$e$（边数）。接下来$e$行，每行一条边。

输出格式

最大匹配数。

输入样例

3 2
1 2
2 3

输出样例

1

提示

• 匈牙利算法：DFS找增广路。
• 或网络流建模。
• 时间复杂度$O(ne)$或$O(\sqrt{n}e)$。