4. (20 pt) Let m1,m2 be two of the men and w1,w2 be two of the women in an instance of the Stable Matching Problem with n men and n women. Assume m1,m2,w1,w2 's preference lists are: m1 's preference: w1>w2> m2 's preference: w2>w1> w1 's preference: m2>m1> w2 's preference: m1>m2> So, we only know the favorite and the second favorite of each of these four persons. (a) (10 pt) Show that if we run Gale-Shapley algorithm with men proposing, then m1 is matched to w1 and m2 is matched to w2. (b) (10 pt) Show that in every stable matching, m1,m2 are matched to w1,w2, i.e., (m1,w1),(m2,w2) or (m1,w2),(m2,w1) must be part of any stable matching