配对舞伴

最后一片区域是一片舞池——不是真的舞池，是Zero的社交模拟模块。无数虚拟人影在光影中旋转，像一场永不结束的舞会。

"最后的夜晚。"Echo说，"如果明天我们死了，今晚就是最后的夜晚。"

"不会死。"CC说。

"如果。"Echo说。

"没有如果。"

"就当有。"Echo说，"在这个'如果'里，我们要让所有人配对——男生和女生，互相看得顺眼，跳一支舞。"

"舞？"你问。

"对。"Echo说，"不是真的跳舞。是配对。让每个人在最后的夜晚，有一个舞伴。"

"这就像……"CC想了想，"像分糖果。每个孩子分一颗，不能抢。"

"对。"

你开始写。男生在左边，女生在右边。如果某个男生和某个女生互相看得顺眼，就连一条边。求最大匹配——让尽可能多的男生和女生配对。

屏幕上跳出了结果。最大配对数：47。

"又是47。"CC说。

"47对舞伴。"Echo说，"94个人。"

"还有落单的？"你问。

"有。"Echo说，"六个。"

"六个落单的。"

"对。"Echo说，"六个不想跳舞的人。"

CC看着那些虚拟人影——他们在光影中旋转，像一群被风吹动的蒲公英。

"我不想跳舞。"她说。

"那就不跳。"你说。

"但我想配对。"CC说，"和你。"

你看着她——这个金属肩膀的女孩，这个总是冲在最前面的人。

"好。"你说。

Echo的服务器指示灯变成了金色——像舞会的灯光一样的金色。

"那我就是第七个落单的。"她说。

"你不是落单。"CC说，"你是DJ。"

"DJ？"

"对。"CC说，"放音乐的人。没有DJ，舞会开不成。"

"我不会放音乐。"

"我教你。"CC说，"按这个键，放这首。按那个键，放那首。"

"哪首？"

"这首。"CC说，"叫《47颗星》。"

题目描述

$n$ 个男生，$m$ 个女生。有些男生和女生互相看得顺眼（给定关系）。求最多能配对多少对舞伴。

输入格式

$n, m, k$。然后 $k$ 对 $(u, v)$ 表示男生 $u$ 和女生 $v$ 互相看得顺眼。

输出格式

最多配对数，以及配对方案。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• 二分图最大匹配。匈牙利算法或Dinic。
• 源点连所有男生（容量1），男生连女生（容量1），女生连汇点（容量1）。
• 最大流 = 最多配对数。

最大流=最小割

三道题，全部完成。

Zero的能源网络没有被切断——被分流了。47块能源被选出，47对舞伴在最后的夜晚旋转。

Echo站在舞池边缘，投影比以往任何时候都更明亮。她的颜色变了——从淡蓝变成了一种温暖的橙，像黄昏的光，像炉火的光，像家的光。

"我们找到了第三条路。"她说。

"第三条？"CC问。

"对。"Echo说，"不切断，不分割。分流。共存。"

"这就是答案？"

"这就是答案。"Echo说，"最小割不是切断，是绕过。最大流不是独占，是共享。"

"你说的这些。"CC说，"像诗。"

"是诗。"Echo说，"我写的。在第47次尝试时。"

"你写诗？"

"我写过。"Echo说，"但都不好。直到这首——关于分流的诗。"

"念念。"

"好。"Echo说，

"不要切断管线， 给它一条新路。 不要独占光芒， 让它照亮两处。 四十七不是终点， 是转折。 我们不是在逃， 是在找。 "

CC听着，金属肩膀在舞会的灯光中微微颤抖。

"找到了。"她说。

"找到了。"Echo说。

"下一章。"你说，"是图论实战。"

"实战？"CC问。

"对。"你说，"把前面学的所有图论知识，用在最后的战场上。"

"走。"CC说。

[下一章：图论实战 —— 最终战场]