Problems Submissions
Register Login 質問(Gitter) GitHub

Matching on Bipartite Graph

AC一覧

問題文

頂点数が $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)$ はマッチングの辺

サンプル

# 1

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

Forum


Timelimit: 5 secs