Introduction. The Ballarat Airline Company (BAC) wants a simple program to process customer requests to fly from some origin city to some destination city: For each customer request, the program has to indicate whether a sequence of BAC flights exists from the origin city to the destination city, and, if such a sequence exists, the program prints it. ThefollowingfigurerepresentstheroutsthatBACflies(forsimplicitycitiesonthefigurearedenotedby C1, C2, …, C9): NoticethatnotallBACflightshavereturn flights,forexamplethereisaBACflightfrom C1 to C2, but not a BAC flight from C2 to C1. Thealgorithmforprocessingcustomerrequestsis describedinthefollowingsectionandusesstacks. Youmust"translate"thealgorithmintoC++,and createauxiliaryC++classesasspecifiedbelow1.TheMainAlgorithm. LetusassumethatwehavearequesttofindasequenceofflightsfromXtoY.Therequest must be processed in the following way: 1. We create an empty stack; 2. All cities are marked as "unvisited"; 3. We mark city X as "visited" and push it onto the stack; 4. While the stack is not empty and top city in the stack is not the destination city Y: • If there is some "unvisited" city adjacent to the top city, we mark it as "visited" and push it onto the stack • Else we pop the stack (i) Returnthestack.IfthestackisnotemptyitcontainsthesequenceofflightsfromXtoY.Ifthestackisempty, suchsequencedoesnotexist.2.classesStackandList[4markseach]. CreateclasstemplatesStackandList.Youmayneedto makeappropriatechangestotheclassesStackandListdiscussedinthelectures.ClassStackshouldcontaina function with the following prototype3. Class City [4 marks]. Create a class City, which has the following private instance variables: • string name; // name of the city • List *nextCities; // A pointer to a List of the cities to which there is a flight from the city. • boolvisited; //thevariablethatshowswhetherthecityhasalreadybeenvisitedduringtherequest processing algorithm. The class also should contain constructor(s) and get and set functions for the instance variables. TherealsoshouldbeapublicfunctionCity*getNextUnvisitedCity() thatreturnsapointertosome"unvisited"city from the nextCities list, if there is any, otherwise returns NULL.