If you are experiencing an issue where math formulas are not displayed, please follow the instructions below.

https://twitter.com/yukicoder/status/1191757446596812800?s=20

Problem Statement

The transportation network of the Tohoku region is represented by $N$ cities and $N - 1$ roads, each of length $1$. It is possible to travel from any city to any other city by following roads.
Maki has $Q$ travel plans, and in the $i$-th travel plan she intends to travel from city $a_i$ to city $b_i$.
However, one day, Kiritan cut some of the roads in the Tohoku region, splitting the region into several connected components. As a result, some travel plans can no longer be carried out.
There are $M$ roads that were not cut, and the $i$-th of them connects city $u_i$ and city $v_i$ bidirectionally. (This sentence was added later.)
So that Maki can carry out all of her travel plans, Itako decided to build an airport in at most one city in each connected component. Travel from an airport to an airport is instantaneous (distance $0$).
When Itako places the airports optimally, find the minimum total distance Maki must travel to carry out all of her travel plans.

Input

$N\ M\ Q$
$u_1\ v_1$
$\vdots$
$u_M\ v_M$
$a_1\ b_1$
$\vdots$
$a_Q\ b_Q$

• $2 \le N \le 10^5$
• $0 \le M \le N - 1$
• $1 \le Q \le 10^5$
• $1 \le u_i, v_i \le N$
  • $u_i \neq v_i$
  • $(u_i, v_i) = (u_j, v_j) \Leftrightarrow i = j$
• $1 \le a_i, b_i \le N$
  • $a_i \neq b_i$
• All input values are integers.

Output

Output the minimum total travel distance as an integer on a single line.

Sample

9 7 3
1 2
1 3
2 4
5 6
5 7
6 8
6 9
2 3
3 5
8 4

7

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

10

3 0 3
1 2
2 3
3 1

0

10 5 7
3 7
10 4
1 4
4 8
5 8
10 1
6 9
5 9
9 2
6 9
7 6
10 1

4