二分图最大匹配

【题目描述】

给定一个有 $L + R$ 个顶点和 $M$ 条边的二分图。第 $i$ 条边为 $(a_i, b_i)$。

请计算最大匹配。

【输入】

$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

【数据范围】

• $1 \leq L, R \leq 100,000$
• $1 \leq M \leq 200,000$
• $0 \leq a_i < L$
• $0 \leq b_i < R$
• 不存在重边。

【来源】

Library Checker（yosupo06） bipartitematching

本题为 special judge（输出任意合法解），暂不可本地评测。