Problem Description

Given a chessboard with $N$ rows and $M$ columns, it is known that some cells are forbidden to place pieces on.

Find the maximum number of rooks that can be placed on the board such that no two rooks can attack each other.

Each rook is placed in a cell, and its attack range is the same as the Chinese chess piece “車”.

Input Format

The first line contains three integers $N,M,T$, where $T$ is the number of forbidden cells.

The next $T$ lines each contain two integers $x$ and $y$, indicating that the cell at row $x$ and column $y$ is forbidden. Rows and columns are numbered starting from $1$.

It is guaranteed that all forbidden cells are distinct.

Output Format

Output one integer, which is the answer.

8 8 0

8

Hint

Constraints: $1 \le N,M \le 200$.

Translated by ChatGPT 5