# Matching on Bipartite Graph

AC一覧

## Problem Statement問題文

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

Calculate the maxmum 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
多重辺は存在しない

## 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)$ はマッチングの辺

## Sampleサンプル

### # 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


Timelimit: 5 secs

Before submitting, please confirm terms and conditions