二分图最大匹配（Matching on Bipartite Graph）

问题描述

给定一个二分图，左部有 $L$ 个顶点（编号 $0$ 到 $L-1$），右部有 $R$ 个顶点（编号 $0$ 到 $R-1$），共 $M$ 条边。第 $i$ 条边连接左部顶点 $a_i$ 与右部顶点 $b_i$。

求该二分图的最大匹配——即边集的最大子集，使得任意两条边不共享顶点。

输出匹配的大小 $K$，以及所选边的列表 $(c_0, d_0), (c_1, d_1), \dots, (c_{K-1}, d_{K-1})$，其中 $c_i$ 属于左部，$d_i$ 属于右部。

约束条件

• $1 \leq L, R \leq 100\,000$
• $1 \leq M \leq 200\,000$
• $0 \leq a_i < L$
• $0 \leq b_i < R$
• 无重边

输入格式

$L\ R\ M$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{M-1}\ b_{M-1}$

输出格式

$K$
$c_0\ d_0$
$c_1\ d_1$
:
$c_{K-1}\ d_{K-1}$

其中：

• $K$ 是最大匹配的边数；
• 每对 $(c_i, d_i)$ 是匹配中的一条边；
• 若存在多解，输出任意一种即可。

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2

3
0 0
1 1
2 2