2. Write a C++ program for hw5_2 that reads an input graph data from a user first. Then, it should present a path for the travelling salesman problem (TSP). In the assignment, you can assume that the maximum number of vertices in the input graph is less than or equal to 8.

**PAY ATTENTION TO OUTPUT**

Input format: This is a sample input from a user. The first line (= 4 in the example) indicates that there are four vertices in the graph. The following four lines describe the names of four cities such as Monterey, LA, SF, and SD. For the problem, you should assume that the first city (= Monterey in the example) is the starting city of the TSP. In addition, you can assume that the city name is always one word. The next line (= 12 in the example) indicates the number of edges in the graph. The remaining 12 lines are the edge information with the "source city", "destination city", and "cost". Thus, the input data describes a directed graph like below: Sample Run 0: Assume that the user typed the following lines 4 Monterey LA SF SD 12 Monterey LA 2 CST370 Page 2 of 5 Monterey SD 7 Monterey SF 5 LA Monterey 2 LA SF 8 LA SD 3 SF Monterey 5 SF LA 8 SF SD 1 SD Monterey 7 SD LA 9 SD SF 1 This is the correct output. Your program should present the path and total cost in separate lines. Path:Monterey->LA->SD->SF->Monterey Cost: 11 Sample Run 2: Assume that the user typed the following lines [Hint]: To solve this problem, you can use all permutations with the cities, except the origin city. For example, there are three cities, LA, SF, and SD in the first sample run, except the origin city Monterey. To make the explanation easy, you can think that LA is number 1, SF is number 2, and SD is number 3. This is all permutations with the three cities 1,2,31,3,22,1,32,3,13,1,23,2,1 For each permutation, you can calculate the cost. For example, in the case of the permutation "1,2, 3", add the origin city at the very beginning and end to the permutation which generates " 0,1,2,3,0 ". This list corresponds to the path "Monterey LASFSD Monterey". Therefore, the cost of this path is "18". Similarly, the next permutation (=1,3,2) corresponds to "Monterey LASDSF Monterey". The cost is 11. This way, you can check all possible paths for the TSP