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
- Boats are very expensive and require a lot of maintenance, we have heard.