Figure 1: Repeated Divorces Algorithm Let a be a perfect matching. while a is not stable do Let (m, w) be an unstable pair with respect to a. Let (m, w') be in a. Let (m', w) be in a. a= (a {(m, w'), (m', w)}) U{(m, w), (m', w')} end while Print a. Needless to say that the above pseudocode indeed produces a stable matching, if it terminates. However, there is no guarantee that it will terminate (and so, it is not really an algorithm). Construct a counterexample, to demonstrate that the above pseudocode will not necessarily terminate. Clearly show the preference list of men and women and an initial perfect matching for your counterexample. Then demonstrate that the pseudocode does not terminate by tracing the execution. Also, specify an actual stable matching for your counterexample, even though the above pseudocode cannot find it. (Hint: Can construct a counterexample with just three men and three women] Figure 1: Repeated Divorces Algorithm Let a be a perfect matching. while a is not stable do Let (m, w) be an unstable pair with respect to a. Let (m, w') be in a. Let (m', w) be in a. a= (a {(m, w'), (m', w)}) U{(m, w), (m', w')} end while Print a. Needless to say that the above pseudocode indeed produces a stable matching, if it terminates. However, there is no guarantee that it will terminate (and so, it is not really an algorithm). Construct a counterexample, to demonstrate that the above pseudocode will not necessarily terminate. Clearly show the preference list of men and women and an initial perfect matching for your counterexample. Then demonstrate that the pseudocode does not terminate by tracing the execution. Also, specify an actual stable matching for your counterexample, even though the above pseudocode cannot find it. (Hint: Can construct a counterexample with just three men and three women]