Rook Attack

Time limit2sMemory limit128 MB

Summary

Given an R by C board with N unusable squares, find the maximum number of non-attacking rooks that can be placed on the remaining squares.

Level: Medium7 of 10
Topics: Graph, BFS, DFS, Math
Solved: No attempts yet

Problem

Sejun has an R×C chessboard with N unusable empty squares. A rook cannot be placed on an unusable square, but such a square does not block attacks. Therefore, two rooks in the same row or the same column can attack each other even if unusable squares lie between them.

Find the maximum number of rooks that can be placed on the board so that no two rooks attack each other. A rook attacks another rook if they are in the same row or in the same column.

Input

The first line contains the number of rows R, the number of columns C, and the number N of unusable empty squares. Each of the next N lines contains the coordinate of one unusable square. Coordinates are given as row and column. The top row is row 1, and the leftmost column is column 1.

R and C are positive integers at most 300, and N is a nonnegative integer at most 600.

Output

Print the maximum number of rooks that can be placed so that no two rooks attack each other.

Examples5

Example 1
Input
```
3 3 6
1 1
2 1
2 2
3 1
3 2
3 3
```
Expected output
```
2
```
Example 2
Input
```
2 2 4
1 1
1 2
2 2
2 1
```
Expected output
```
0
```
Example 3
Input
```
8 8 0
```
Expected output
```
8
```
Example 4
Input
```
3 3 3
1 1
2 3
3 3
```
Expected output
```
3
```
Example 5
Input
```
200 200 0
```
Expected output
```
200
```