Stable Marriage Problem: There are n men and n women, where each person has ranked all members of the

Stable Marriage Problem: There are n men and n women, where each person has ranked all members
of the opposite sex in order of preference. You want to pair them up to make stable matching that
there are no two people of opposite sex who would both rather have each other than their current
partners.
Write Java program using Gale-Shapley algorithm which will receive an instance of the marriage
problem and return a stable matching when
a) men propose to women
b) women propose to men

Input Format: Create input1.txt file in the same directory as the java and class files.
“input1.txt” will be entered as a command line argument. The first line will be n(the number of
women or men). The next n lines will be the preference lists of the men and the fallowing n
lines will be the preference lists of the women with a whitespace separated list from best to
worst.
Output Format: Your program will output a stable matching for when men propose to women and
another stable matching for when women propose to men.
Examples:
If input1.txt contains:
2
1 2
2 1
2 1
1 2
Then output will be:
Output when men propose:
{(1,1), (2,2)} → It means {(m1, w1), (m2, w2)}
Output when women propose:
{(1,2), (2,1)} → It means ((w1, m2), (w2, m1)}

If Input1.txt contains:
3
1 2 3
2 1 3
1 2 3
2 1 3
1 2 3
1 2 3
Then output will be:
Output when men propose:
{(1,1), (2,2), (3,3} → It means {(m1, w1), (m2, w2), (m3, w3)}
Output when women propose:
{(1,2), (2,1), (3,3)} → It means ((w1, m2), (w2, m1), (w3, m3)}

Note:
Your Java program should be commented, indented, and structured. Output should be sent to
System.out. Please place all your files (.java, .class, .txt) in a directory named after you, zip them and
submit them to canvas. Don’t include any extra files and directories from IDE environment. The
program must compile with the command javac *.java and run with the command java Project1
input1.txt. Remember input1.txt is a command line argument.
Don’t place the classes in a package (use default package).