2. (25) [Connected graph with a distant node pair] Textbook Exercise 9 in Chapter 3. Use the BFS algorithm as the base of your algorithm design. Consider the following hints to prove the existence of a "hot spot" node v without which there is no path between two "distant" nodess and t: (i) BFS always finds the shortest path to every node from the source;(ii the shortest path length to any node equals the number of BFS layers to the layer containing the node;iii) property (3.4) on page 81 of the textbook. 9. There's a natural intuition that two nodes that are far apart in a com- munication network-separated by many hops-have a more tenuous connection than two nodes that are close together. There are a number of algorithmic results that are based to some extent on different ways of making this notion precise. Here's one that involves the susceptibility of paths to the deletion of nodes. Suppose that an n-node undirected graph G=(V,E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to eithers or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by deleting v contains no path from s to t.) Give an algorithm with running time O(mn) to find such a node v