Let G =(V,E) be a directed graph with edge lengths that can be negative. Let `(e) denote the length of edge eE 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 uV 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 `(e) before T is not a valid shortest path tree in G. Briey 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 outputif no amount of increase will change the shortest path tree. Briey justify the correctness of your solution.