C++

In the Settlers of Catan, you can't place a settlement within two spaces of another settlement. In this advanced version of Catan, the rules are a little different. You can't place a settlement in a location that is within k spaces of all existing settlements (or on top of an existing settlement). (So a settlement that is within k spaces of some existing settlements but not every existing settlement is legal.) Your task is, given a board and a number k, determine the number of offlimit locations for a settlement.

Input Format

The first line contains an integer k, distance required from settlements. The next line contains an integer x, the number of settlements. The next x lines contain the unique identifiers for those k settlements. The following line contains an integer n, the number of positions on the board. The next n lines contain a unique identifier for that position, followed by a colon, followed by a comma-separated list of adjacent positions. For example:

3 4 1 2 5 22 24 1: 2, 6, 7 2: 1, 3, 10 3: 2, 4, 13 4: 3, 5, 16 5: 4, 6, 19 6: 5, 1, 22 7: 1, 8, 24 8: 7, 9 9: 8, 10 10: 2, 9, 11 11: 10, 12 12: 11, 13 13: 3, 12, 14 14: 13, 15 15: 14, 16 16: 4, 15, 17 17: 16, 18 18: 17, 19 19: 5, 18, 20 20: 19, 21 21: 20, 22 22: 6, 21, 23 23: 22, 24 24: 23, 7 

Constraints

You may assume the positions form an undirected, connected graph.

Output Format

A single line containing an integer indicating the number of invalid settlement locations. For example, for the above input:

7 

Sample Input 0

2 2 3 6 24 1: 2, 6, 7 2: 1, 3, 10 3: 2, 4, 13 4: 3, 5, 16 5: 4, 6, 19 6: 5, 1, 22 7: 1, 8, 24 8: 7, 9 9: 8, 10 10: 2, 9, 11 11: 10, 12 12: 11, 13 13: 3, 12, 14 14: 13, 15 15: 14, 16 16: 4, 15, 17 17: 16, 18 18: 17, 19 19: 5, 18, 20 20: 19, 21 21: 20, 22 22: 6, 21, 23 23: 22, 24 24: 23, 7 

Sample Output 0

6