Let G(V,E) be an undirected graph with n vertices and m edges such that G has two vertices s and t where the shortest path from s to t has length strictly more than n/2. Then, prove that there must be a vertex w ∈ V  {s,t} such that every path from s to t must pass through w. Furthermore, assuming that G is given to you in the adjacency-list representation along with vertices s and t, design an O(n + m) time algorithm to output such a vertex w. 4. Let G(V.E) be an undirected graph with n vertices and m edges such that G has two vertices s and t where the shortest path from s to t has length strictly more than n/2. Then, prove that there must be a vertex w e V{s,t} such that every path from s to t must pass through w. Furthermore, assuming that G is given to you in the adjacency-list representation along with vertices s and t, design an O(n + m) time algorithm to output such a vertex w.