Problem 1: Long Paths are Vulnerable The city metro system is composed of a series of stations and segments that connect different sta- tions. The whole city is connected in such a way that it is possible to travel from every station to every other station in the city. In fact, in an effort to ensure the city does not fall into chaos in case of unexpected service outages, there are many cases in which you could reach your desired destination following more than one route. There are a total of n stations in the whole city. Emily is an ECE student that lives in North Station, which is quite far from University Station. In fact, the shortest route between North Station and University Station happens to be of length +1, where the length of a path is the number of its segments/hops. Since Emily is taking Algorithms, she realizes that this fact makes commute quite vulnerable. (a) Prove that there is at least one station in the metro system which, by going out of service, will cause the whole city to not be connected, such that Emily will not be able to make it to the university Hint: The BFS tree will have some important feature here. (b) Provide an algorithm to find one of these critical metro stations that would create a discon- nected city if it were to suffer an outage. Your algorithm should run in O(n + m) time