New update is available. Click here to update.

# Count Nodes within K-distance

Posted: 28 Dec, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### Example:

``````Marked Nodes are Circled with red colour.

Now consider this example of the graph. Here nodes 1,2, and 4 are marked, and let us take the value of K as 3, i.e., we have to find all the nodes at a distance less than 3 from all the marked nodes. We can see that nodes with index 5,9,8,2,0,7 have distances less than 3 from all marked nodes; therefore, the total count of nodes will be 6.
``````
##### Input format :
``````The first line contains two space-separated integers 'V' and 'E', denoting the number of vertices and edges in the graph.

The next 'E' lines contain two space-separated integers denoting the vertices between whom edges exist.

The next line contains a single integer 'K' denoting the distance.

The next line contains a single integer 'M' representing the number of marked nodes in the graph.

The next line contains 'M' space-separated integers representing marked nodes.
``````
##### Output format :
``````For each test case, print an integer denoting the count of the nodes which are less than 'K' distance from all the marked nodes.

The output of every test case will be printed in a separate line.
``````
##### Note:
``````You don’t have to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= 'V' <= 10^4
0 <= 'E' <= 10^4
1 <= |'V'| <= 'V'
1 <= 'K' <= 35000
1 <= 'M' <= 7000

Time Limit: 1 sec.
``````