Each edge in the graph has weight of 1,The graph may have cycles ,if a node has self loop it can be any distance from itself from 0 to infinity , depending on the no. of time we take the self loop.

We ll be asked multiple queries on a given graph of the form (distance , source) and the o/p is the list of nodes that are exactly at the given distance starting from the source vertex.

Constraints

1<=Nodes<=500 1<queries<=500 1<=distance<=10^9 I have a feeling ,there would be many repeated computations as the no. of nodes are small,but i am not able to figure out how do i reduce the problem in smaller problems.

What is the efficient way to do this?

I have solved the problem using bfs, but the constraint on distance is in order of 10^9 ,hence bfs is slow.

I have also tried using matrix exponentiation but its too slow ,for the given constraints. The problem has a time limit of 1 sec.