Idea: Given an instance of StableMatching and a match determine whether the match is stable and if not give
one instability.
Input Format: The input file will be called input1.txt and be in the same directory as the java and class files.
Line 0 will be a single integer n, the number of men (or women). Lines 1 to n will be the preferences of the n men
where each line is a space seperated permutation of {1, 2, . . . , n}. Lines n + 1 to n + n will be the preferences of
the n women where each line is a space seperated permutation of {1, 2, . . . , n}. Line 2n + 1 will be a permutation
of {1, 2, 3, . . . , n} which represents a matching. In particular, the ith item in the permutation is the number of the
woman with which man i is matched.
Output: Yes (if the match is stable) or No and an ordered pair representing an instability (if the match is unstable).
Examples: If there were 2 men (and women), both men prefered woman 1, both women prefered man 1, and you
wanted to check the match M1-W1, M2-W2 then the input would be
2
1 2
1 2
1 2
1 2
1 2
and the output would be
Yes
because the matching is stable.