Hide

Problem A
Sailing Friends

A common saying goes that if you like sailing, it is much better to have a friend with a boat rather than being the friend with a boat.1

Being mathematically inclined, you have realized that this property applies recursively – it is much better to be the friend of a friend with a boat rather than having a boat, and so on.

In a small coastal city, there are $N$ people, of which $B$ already have boats. Among them, $M$ pairs of people are friends with each other. You start to wonder, what is the smallest amount of people who would have to buy a boat so that everyone in the city either owns a boat or could borrow one from a friend (possibly indirectly through a friend of a friend of a …)?

Input

The first line contains the integers $N$ ($1 \le N \le 100\, 000$), $B$ ($0 \le B \le N$), $M$ ($0 \le M \le 200\, 000$), as described in the statement.

The next line contains $B$ integers – the 1-indexed numbers of everyone with a boat.

The final $M$ lines describe the pairs of friends. Each line contains the numbers of two friends $1 \le a \neq b \le N$, separated by spaces.

Output

Output a single integer – the number of additional people who must buy a boat.

Sample Input 1 Sample Output 1
3 1 1
1
2 1
1
Sample Input 2 Sample Output 2
4 2 2
1 2
2 1
3 4
1
Sample Input 3 Sample Output 3
4 0 2

2 1
4 3
2

Footnotes

  1. Boats are very expensive and require a lot of maintenance, we have heard.

Please log in to submit a solution to this problem

Log in