P10937 Rook Placement.

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 “車”.

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 one integer, which is the answer.

Constraints: $1 \le N,M \le 200$. Translated by ChatGPT 5