1. Let T be a depth-first search tree of a graph. Let D (i) denote an ordered set of descendants of the node i ∈ T, arranged in the same order in which the depth-first search method labeled them. Define last(i) as the last element in the set D (i). Modify the depthfirst search algorithm so that while computing the depth-first traversal of the network G, it also computes the last index of every node. Your algorithm should run in O(m) time.
2. Longest path-in a tree (Handler, 1973). A longest path in an undirected tree T is a path containing the maximum number of arcs. The longest path can start and end anywhere. Show that we can determine a longest path in T as follows: Select any node i and use a search algorithm to find a node k farthest from node i. Then use a search algorithm to find a node I farthest from node k. Show that the tree path from node k to node I is a longest path in T.