Alliance

Long, long ago, in a distant galaxy, there were two states that decided to form an alliance. Each state consisted of a number of planets. Some of the planets were connected by convenient first-generation hyperspace tunnels; each tunnel joined two planets and let passengers travel between them in a short time.

One day scientists discovered second-generation hyperspace tunnels, which allowed even faster travel. Upgrading an old tunnel to a second-generation one cost the same everywhere. The politicians of both states decided to strengthen the alliance by upgrading some of the first-generation tunnels that connected planets from different states. So that no planet would feel slighted, they ruled that every planet already holding at least one first-generation tunnel to a planet of the opposite state must have at least one of those tunnels upgraded. They set the plan in motion, but spent far too much money: both states went bankrupt, the alliance collapsed, and cosmic chaos overtook the galaxy.

Today some historians studying those events believe that too many tunnels were upgraded and that the whole mess could have been avoided. They would like to know the minimum number of tunnels that had to be upgraded to satisfy the politicians' conditions. Your task is to help them.

Write a program that:

• reads the description of the first-generation tunnel network from standard input,
• finds the minimum number of tunnels that had to be upgraded to satisfy the conditions set by the politicians,
• writes the result to standard output.

The first line contains two integers $m$ and $n$, separated by a single space, giving the number of planets in the first and second state respectively, with $1 \le m, n \le 2000$. The planets of the first state are numbered with the integers from $1$ to $m$, and the planets of the second state with the integers from $m+1$ to $m+n$. The second line contains one integer $k$ with $1 \le k \le 10000$, the number of first-generation tunnels. Each of the next $k$ lines describes one tunnel and contains a pair of integers $a$ and $b$, separated by a single space, where $a$ and $b$ are the numbers of the two planets joined by that tunnel. No tunnel connects a planet with itself, and no pair of planets is connected by more than one tunnel.

In the first and only line of output, print a single integer: the minimum number of tunnels that had to be upgraded.