Minimum Additional Roads

You are given a kingdom with n cities and m existing roads connecting some pairs of cities. In addition, there are k pivotal pairs of cities. A direct road must exist between each pivotal pair. If a pivotal pair is not directly connected by an existing road, a new road must be constructed. After ensuring all pivotal pairs have a direct road, the kingdom must also be fully connected (any city can be reached from any other city).

Your task is to determine the minimum number of additional roads required such that:

• For each pivotal pair (a, b), there is a direct road between city a and city b.
• The entire kingdom becomes connected.

The final answer is given by the formula:

$$answer = |P| + (C - 1)$$

where $$|P|$$ is the number of pivotal roads that needed to be added because they were missing, and C is the number of connected components in the graph after adding the pivotal roads.

inputFormat

The input is read from stdin and has the following format:

 n m k
 u1 v1
 u2 v2
 ...
 um vm
 a1 b1
 a2 b2
 ...
 ak bk

Where:

• n (integer): the number of cities, cities are labeled from 1 to n.
• m (integer): the number of existing roads.
• k (integer): the number of pivotal pairs.
• The next m lines each contain two integers u and v, representing an existing road between cities u and v.
• The following k lines each contain two integers a and b, representing a pivotal pair that must be directly connected.

outputFormat

The output should be written to stdout and is a single integer: the minimum number of additional roads required.

## sample

6 5 2
1 2
1 3
2 3
4 5
5 6
1 4
3 6

2