Can you answer this question:

The definition of stability was motivated by being worried that the solution by the algorithm would be overridden by pairs comprising a woman and a man this could lead to a chain of further overrides, until the solution has nothing to do with the one output by the algorithm any more. When we addressed this, we were worried about overrides (or "backroom deals") involving a man and woman. But we might also be concerned about backroom deals between two men (who want to swap their assigned women) or two women (who want to swap their assigned men). Going back to the example of universities, this could be two students who trade their admissions, or two universities who trade students. We will focus on instances with the same number of men and women (so we can talk about perfect matchings again), and define these new notions of stability as follows:

Men-Stable, Women-Stable. Given the rankings of all men and all women. We say that a perfect matching M between n men and n women is men-stable if there are no two men m, m who prefer each other's partner over their own. We say that M is women-stable if there are no two women w, w who prefer each other's partner over their own.

(a) Show that there are inputs (i.e., preferences) where no perfect matching exists that is both men-stable and women-stable simultaneously