QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓
[+5]

# 898. 二分图最大匹配

Statistics

Source: Library Checker

Statements

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

Calculate the maxmum matching.

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

Constraints

  • 1L,R100,000
  • 1M200,000
  • 0ai<L
  • 0bi<R
  • There is no multiple edges (多重辺は存在しない)

Input

  • L R M
  • a0 b0
  • a1 b1
  • :
  • aM1 bM1

Output

  • K
  • c0 d0
  • c1 d1
  • :
  • cK1 dK1

K is the number of maximum matching, and (ci,di) is the edge of the matching.

K は最大マッチングの本数、(ci,di) はマッチングの辺

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