Lizard and Amarillo are street racers. Their city is given by a directed graph G. For each edge e, they have average times L(e) and A(e) that it takes them to traverse that edge. Howard is trying to fix a race in Amarillos favor. To do so he needs to find a course for this race (which must start and end at the same place) so that Amarillos average time to complete the course is smaller than Lizards. Give an algorithm to determine whether or not this is possible to do. Your runtime should be where n is the # of vertices/locations in G.

Use the Negative Weight cycle finding algorithm as a black-box subroutine.

Describe your algorithm in words and write a pseudocode and analyze the runtime.