3. (4 points) Slow case of the Ford-Fulkerson algorithm. In class we mentioned that the Ford-Fulkerson algorithm takes O(F) iterations, where F is the value of the maximum flow. Note that the value of F can be much larger than n and m. In this problem we will see that this can happen, even when we push as much flow as possible along the s t path found in the residual graph. Let Z be an arbitrarily large integer. Consider the directed network on 4 vertices, s, a, b, and t with (capacitated) edges #5 a with capacity Z. s b with capacity Z. a t with capacity Z. b t with capacity Z. a b with capacity 1. The maximum flow is 27: sending Z units each along the two paths s a t and s b t. Furthermore, if we return s a t as our first augmenting path, we willroute Z units on it, so the Ford-Fulkerson algorithm can potentially terminate in 2 iterations (plus 1 more to output the minimum cut) , Instead, suppose our path finding algorithm in the residual graphs always finds a path involving a-> b or b a if it exists. Draw the first 2 residual graphs, and infer from them (with a brief justification) the number of iterations (in terms of Z) that the Ford-Fulkerson algorithm may take on this graph. 3. (4 points) Slow case of the Ford-Fulkerson algorithm. In class we mentioned that the Ford-Fulkerson algorithm takes O(F) iterations, where F is the value of the maximum flow. Note that the value of F can be much larger than n and m. In this problem we will see that this can happen, even when we push as much flow as possible along the s t path found in the residual graph. Let Z be an arbitrarily large integer. Consider the directed network on 4 vertices, s, a, b, and t with (capacitated) edges #5 a with capacity Z. s b with capacity Z. a t with capacity Z. b t with capacity Z. a b with capacity 1. The maximum flow is 27: sending Z units each along the two paths s a t and s b t. Furthermore, if we return s a t as our first augmenting path, we willroute Z units on it, so the Ford-Fulkerson algorithm can potentially terminate in 2 iterations (plus 1 more to output the minimum cut) , Instead, suppose our path finding algorithm in the residual graphs always finds a path involving a-> b or b a if it exists. Draw the first 2 residual graphs, and infer from them (with a brief justification) the number of iterations (in terms of Z) that the Ford-Fulkerson algorithm may take on this graph