Rook Attack#2904
You are given a chessboard with rows and columns. Several squares on the board have been cut out, and their coordinates are given. You must place the maximum possible number of rooks on the chessboard so that no two rooks attack each other. A rook can attack all squares in the same row or column as itself. Rooks cannot be placed on cut out squares. The cut out squares do not block the path of rooks.
The input consists of multiple test cases. The first line of each test case contains three integers: the number of rows , the number of columns (1 \leq rows, cols \leq 300), and the number of cut out squares . The next line contains a list of the coordinates of the cut out squares, separated by spaces. The list is given as x_1~y_1~x_2~y_2~x_3~y_3~\ldots~x_{cuts}~y_{cuts}. It is guaranteed that 0 \leq x_i \leq rows - 1,~0 \leq y_i \leq cols - 1.
For each test case, output on a separate line the maximum number of rooks that can be placed on the chessboard such that no two rooks attack each other.
Example 1