1. (60 pts) In this problem, there are many cities separated by rivers, and some villages in the cities which are represented as vertices of the undirected graph as shown below. You will build some bridges to connect the cities, however a minimum number of bridges is required to solve this problem. 8 7 9 1 2 5 15 3 6 (14 4 10 11 12 13 In the figure, there are 15 villages and 4 cities. All villages are numbered from 1 to 15, as well as some of them are connected by edges. a)(10 pts) How many bridges do we need to build to visit any village starting from the 1st village? Explain why. b)(15 pts) Explain how we can programmatically find out how many cities we have in the graph above. You can suggest a familiar graph algorithm. c)(30 pts) Design and implement an algorithm to find the minimum number of bridges in accordance with your explanation in (a), write its code in MIN_BRIDGES function. Use the algorithm you suggested in (b) to find the number of cities MIN_BRIDGES (graph, n) return num_of_bridges In the function, graph is the adjacency list (e.g. 1:[2,3], 11:[12,13), 14:[15]) of the graph. This graph consists of 15 villages as seen in the image above. Second parametern is the number of villages, and the returned value num_of_bridges is an integer specifying the number of bridges. Hint: You can solve this problem with just 15-20 lines of code. d)(5 pts) What is the worst-time complexity for your proposed solution