Description

Given a bipartite graph with $n$ left vertices, $m$ right vertices, and $e$ edges, find the size of its maximum matching.

The left vertices are numbered from $1$ to $n$, and the right vertices are numbered from $1$ to $m$.

Input Format

The first line contains three integers, representing $n$, $m$, and $e$.

The next $e$ lines each contain two integers $u, v$, indicating that there is an edge connecting left vertex $u$ and right vertex $v$.

Output Format

Output a single integer on one line, representing the size of the maximum matching of the bipartite graph.

1 1 1
1 1

1

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

2

Hint

Constraints

For all test points, it is guaranteed that:

• $1 \leq n, m \leq 500$.
• $1 \leq e \leq 5 \times 10^4$.
• $1 \leq u \leq n$, $1 \leq v \leq m$.

The given graph is not guaranteed to be free of multiple edges.

Translated by ChatGPT 5