Maximum Non-Conflicting Green Signals

You are given an intersection grid with M rows and N columns. At certain intersections, there are traffic signals. Your task is to determine the maximum number of traffic signals that can be turned green such that no two green signals are in the same row or the same column.

Formally, you are provided with a grid of size \( M \times N \) and a list of coordinates representing the locations of traffic signals. You must choose a subset of these signals to set to green, ensuring that no two selected signals share the same row or the same column. Output the maximum number of green signals that can be set without any conflicts.

Note: Rows and columns are 0-indexed.

inputFormat

The input is provided via standard input (stdin) with the following format:

• The first line contains two space-separated integers \( M \) and \( N \), representing the number of rows and columns.
• The second line contains a single integer \( K \), the number of traffic signals.
• Each of the next \( K \) lines contains two space-separated integers \( x \) and \( y \) which denote the row and column indices of a traffic signal.

It is guaranteed that \( 0 \le x < M \) and \( 0 \le y < N \) for all signals.

outputFormat

Output a single integer to standard output (stdout), which is the maximum number of non-conflicting green signals that can be activated.

4 4
4
0 1
1 3
2 0
3 2

4