2. Let G = (V, E) be a directed graph with edge lengths that can be negative. Let 1 (e) denote the length of edge e E E and assume it is an integer. Assume you have a shortest path tree T rooted at a source node s that contains all the nodes in V. You also have the distance values d(s, u) for each u E V in an array (thus, you can access the distance from s to u in O(1) time). Note that the existence of T implies that G does not have a negative length cycle. . Let e = (p, q) be an edge of G that is not in T. Show how to compute in O(1) time the smallest integer amount by which we can decrease l(e) before T is not a valid shortest path tree in G. Briefly justify the correctness of your solution. . Let e = (p, q) be an edge in the tree T. Show how to compute in O(m + n) time the smallest integer amount by which we can increase (e) such that T is no longer a valid shortest path tree. Your algorithm should output oo if no amount of increase will change the shortest path tree. Briefly justify the correctness of your solution. The example below may help you. The dotted edges form the shortest path tree T and the distances to the nodes from s are shown inside the circles. For the first part consider an edge such as (b, d) and for the second part consider an edge such as (f,e) 3 6 0