C++ or Java:

Write the program that modifies Breadth First Search in such a way that given an undirected connected graph G, and a starting node s, it will print for every node v the length of the shortest path from s to v and also the number of shortest paths from s to v (For example, if G is the graph from problem 1, the length of a shortest path from 1 to 7 is 3, and there are three shortest paths from 1 to 7, namely 1-2 5-7, 1 3-5-7 and 1-4-6-7). Test your program on the graph Gi from problem 1 and for the following graph G2: and report the results you have obtained for these two graphs