Problem description provided:
Agent Ω - found valuable intel on C.H.I.M.E.R.A. in the underground warehouse. But she also discovered that the other swarms destroyed more warehouses in other locations.
The first warehouse was tough to clear. There was radiation (which could be avoided with a Giger counter) and damaged life support (so space suits were required) making the overall effort much higher than she expected. As such, Agent Ω decided to be more careful when clearing out the other warehouses. Rather than needing to find a path to EVERY storage room, she decided to pick a smaller number of KEY storage rooms to get to. Additionally, the tunnels all turned out to be easy to clear - it was the storage rooms themselves that were the harder part.
Can you determine the FEWEST total storage rooms that Agent Ω will need to clear in order to have all of the key storage rooms connected? You may assume the single entrence leads into one of the key storage rooms, so you don't need to consider it separately.
Hint: you will need to use a branch-and-bound approach to solving this problem.
NOTE 1: This problem is worth 400 points. Any points beyond that are extra credit. That said, the test cases get substantially more difficult as you go into the extra credit range.
The description provided for this problem:
NOTE 2: Your program must always either output the correct answer or timeout while searching. If your program every outputs an actively incorrect response for any test case, it will receive 0 credit on this problem (regardless of how many test cases it passes). Test cases on which you time out will not provide points, but will also not zero out points earned on other test cases.
Input Format
The first line contains three values: the number of storage rooms (N), the number of tunnels (M), and how many of those storage rooms are key [K]
The next M lines each describe a tunnel, indicating the unique id of each storage room it connects.
The final K lines each provide a single key vertex.
Constraints
1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
1 ≤ K ≤ N
0 ≤ Storage Room IDs < N
Output Format
A single number indicating the minimum number of storage rooms that need to be cleared for all of the key storage rooms to be cleared as well as any others needed to make sure that they are all connected.
Example 0
Sample Input
5 6 2
0 1
0 2
0 4
1 4
2 3
2 4
0
3
Sample Output
3
Explanation
If room 0, 2, and 3 are all cleared then both keys (0 and 3) will be clear as will a room that will connect them (2).
