QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓

# 898. 二分图最大匹配

Statistics

Source: Library Checker

Statements

Given a bipartite graph with $L + R$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$.

Calculate the maxmum matching.

頂点数が $L, R$、辺が $M$ の二部グラフが与えられる。$i$ 番目の辺は $(a_i, b_i)$ である。 最大マッチングを求めてください。

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 (多重辺は存在しない)

Input

  • $L$ $R$ $M$
  • $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.

$K$ は最大マッチングの本数、$(c_i, d_i)$ はマッチングの辺

Example

Input

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

Output

3
0 0
1 1
2 2