Beacon Coverage on Hills

In this problem, you are given a kingdom with (n) hills and (p) bidirectional roads connecting them. The hills are numbered from 1 to (n). Additionally, you are provided with a list of candidate hills where beacons can be placed. A beacon placed on a hill will cover the hill itself and all hills directly connected to it by a road. You are also given an integer (k) which represents the maximum number of beacons that can be used. Note that if (k \ge n), it is possible to cover all the hills by placing a beacon on every hill, so the answer is simply (n). Otherwise, if placing beacons on all the candidate hills covers all the hills, then the answer is the number of candidate hills used; if not, output (-1).

inputFormat

The input is given via standard input (stdin) and has the following format:\ (n) (k)\ (m)\ (b_1) (b_2) ... (b_m)\ (p)\ The next (p) lines each contain two integers (u) and (v), representing a bidirectional road between hill (u) and hill (v).\ \ Here, (n) is the total number of hills, (k) is the maximum number of beacons available, (m) is the number of candidate hills for beacon placement, and (p) is the number of roads.

outputFormat

Output a single integer to standard output (stdout). This integer is the minimum number of beacons required to cover all the hills. If it is not possible to cover all the hills using the candidate beacon positions, output (-1).## sample

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

2