$(20$ points$)$ Let $G=(V,E)$ be a flow network with source $s,sinkt,$ and

integer capacities. Suppose that we are given a maximum flow in $G.$ Let

$n$ and $m$ be the numbers of vertices and edges in $G,$ respectively.

$($a$)(10$ points$)$ Suppose that the capacity of a single edge $(u,v)inE$

is increased by $1.$ Give an $O(m+n)-$time algorithm to update the

maximum flow. Explain why your algorithm produces a maximum

flow.

$($b$)(10$ points$)$ Suppose that the capacity of a single edge $(u,v)inE$

is decreased by $1.$ Give an $O(m+n)-$time algorithm to update the

maximum flow. Explain why your algorithm produces a maximum

flow.