Consider an instance of the stable matching problem with n men and n women. Let X and Y be some two stable matchings for this instance. We now construct a new pairing Z as follows. For each man m, if X pairs him with a woman w^m_x and Y pairs him with a woman w^m_y then in Z the man is paired with the woman he prefers most among w^m_x and w^m_y. Note that w m x and w m y could be the same woman.

A) Prove or disprove that Z is a stable matching.

B) Now consider a pairing Z' in which a man m is paired with the woman he prefers the least among w^m_x and w^m_y. Prove or disprove that Z' is a stable matching.