8211: [yosupo] Graph - Matching on Bipartite Graph
[Creator : ]
Description
Given a bipartite graph with $L + R$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$.
Calculate the maxmum matching.
Calculate the maxmum matching.
Input
$L$ $R$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{M - 1}$ $b_{M - 1}$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{M - 1}$ $b_{M - 1}$
Output
$K$
$c_0$ $d_0$
$c_1$ $d_1$
:
$c_{K - 1}$ $d_{K - 1}$
$K$ is the number of maximum matching, and $(c_i, d_i)$ is the edge of the matching.
$c_0$ $d_0$
$c_1$ $d_1$
:
$c_{K - 1}$ $d_{K - 1}$
$K$ is the number of maximum matching, and $(c_i, d_i)$ is the edge of the matching.
Constraints
$1 \leq L, R \leq 100,000$
$1 \leq M \leq 200,000$
$0 \leq a_i < L$
$0 \leq b_i < R$
There is no multiple edges.
$1 \leq M \leq 200,000$
$0 \leq a_i < L$
$0 \leq b_i < R$
There is no multiple edges.
Sample 1 Input
4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2
Sample 1 Output
3
0 0
1 1
2 2