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
- 1≤L,R≤100,000
- 1≤M≤200,000
- 0≤ai<L
- 0≤bi<R
- There is no multiple edges (多重辺は存在しない)
Input
- L R M
- a0 b0
- a1 b1
- :
- aM−1 bM−1
Output
- K
- c0 d0
- c1 d1
- :
- cK−1 dK−1
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