Given a set of airports and connections corresponding to an air transportation network. Specifically, you know if there is a direct connection between any two airports in the network.

1. Complete the function below, flightLegs, so that it efficiently computes the minimum number of flights required to travel between two distinct airports on the network. The function should also efficiently determine the number of distinct routes between the two airports which require this minimum number of flights. The function is provided with an N- element adjacency list, Alist, as input, and airports are numbered from 0 to N-1. The ith element of Alist is a list containing the airports which can be reached directly from airport i. The network is symmetric, so if i can be reached directly from j, then j can be reached directly from i. The starting (start) and destination (dest) airports are also provided. The function output should be a two-element list containing the minimum number of flights required to travel between start and dest and the number of distinct journeys between start and dest with this minimum number.

def flightLegs(Alist,start,dest): """ Find the minimum number of flights required to travel between start and dest, and determine the number of distinct routes between start and dest which require this minimum number of flights. Input: Alist: Adjacency list for airport network start, dest: starting and destination airports for journey. Airports are numbered from 0 to N-1 (inclusive) where N = len(Alist) Output: Flights: 2-element list containing: [the min number of flights between start and dest, the number of distinct jouneys with this min number] Return an empty list if no journey exist which connect start and dest """ Flights = [] #modify as needed return Flights

2. Finally, discuss the running time and efficiency of your implementation. The discussion should include an estimate of the asymptotic running time and a concise description of how you constructed this estimate. You should also include a brief description of each algorithm.