Optimal Pilot Pairing

You are given n pilots, among which m are foreign pilots and n-m are British pilots. The foreign pilots are numbered from \(1\) to \(m\) and the British pilots are numbered from \(m+1\) to \(n\). For a given list of compatible pilot pairs between a foreign pilot and a British pilot, design an algorithm to determine the optimal pairing scheme such that the Royal Air Force can dispatch the maximum number of planes in one operation.

The compatibility between a foreign pilot and a British pilot is given. A valid pairing is one in which a foreign pilot is paired with a British pilot with whom he is compatible. Each pilot can participate in at most one pair. The objective is to maximize the number of pairs.

Note: Use the bipartite matching technique where the left set represents foreign pilots and the right set represents British pilots. The problem can be solved using a DFS-based augmenting path algorithm.

inputFormat

The input consists of the following:

1. The first line contains two space-separated integers \(n\) and \(m\), where \(n\) is the total number of pilots and \(m\) is the number of foreign pilots.
2. The second line contains a single integer \(k\), the number of compatibility pairs.
3. Each of the next \(k\) lines contains two space-separated integers \(a\) and \(b\) indicating that foreign pilot \(a\) (where \(1 \leq a \leq m\)) is compatible with British pilot \(b\) (where \(m+1 \leq b \leq n\)).

outputFormat

Output a single integer representing the maximum number of pilot pairs (i.e. the maximum number of planes that can be dispatched).

sample

2 1
1
1 2

1