Using Python, you will write a program called critical-path.py that implements Algorithm 6.3 (Critical path), page 163 of our textbook.

Read carefully Exercise 3, page 168, which gives background information for this programming assignment.

Note that Algorithm 6.3 calls TopologicalSort (see Algorithm 6.2), which in-turn calls DFSTopologicalSort (see Algorithm 6.1).

Algorithm 6.3 (Critical path) employs an an adjacency list structure, which you have implemented previously in one or more programming assignments. (Recall that an adjacency list essentially is a "list of lists"; namely, a list of linked lists.) You may implement your adjacency list using any (i.e., your preferred) approach. Be sure to store the node numbers and their associated weights.

IMPLEMENTATION DETAILS:

Be sure to include your name, along with the Certificate of Authenticity, as comments at the very beginning of your Python code. Also, if you collaborated with others, be sure to state their names as well.

Your program MUST validate user input, thus informing the user of invalid input data.

Your program should display the following menu (looping continuously until the user selects option E):

Enter the letter below that corresponds to the desired singly-linked list operation:

A. Input a task scheduling graph, G, similar to Figure 6.9 (p. 160), and generate the adjacency list for graph G.

B. Calculate and print the nodes that are on the critical path.

C. Print the adjacency list (i.e., the list of singly-linked lists) for graph G.

D. End program.

**Note: Your menu logic should accept options A, B, C, D (uppercase or lowercase). Anything other than these options should generate the following error message to the user:

Invalid option! Please enter A, B, C or D.