CODE MUST BE IN JAVA

Details: Your java program will be provided with a file called input.txt which describes an instance of STA$-$

blemarriage. To be more specific, the first line will be a single integer $N($the number of men$/$women$),$ the

next $N$ lines will give the preference lists of the $N$ men $($ie each line will be a permutation of $\{1,2,3,$dots,$N\})$

and the final $N$ lines will give the preference lists of the $N$ women.

You must write a java program which will read in the input from the file input.txt $($which will be placed

in the same directory as your java program$),$ find the matching $($on $2N$ men and women$)$ that occurs if

ProposeDispose and SadieHawkins are both run on one copy of the given input, output the number of

men who get a different partner than their clone, output the number of women who get a different partner

than their clone, and determine whether the combined matching on the $2$ N men and women is stable.

Picky, but required specifications: Your project must:

be submitted via canvas.

consist of $1$ or more dot$-$java files $($no class files, zip files, input files, or other files should be submit$-$

ted$).$

have each file begin with a comment containing your name and the project number.

not be placed into any package.

have one file called Project$1.$java $($don$\text{'}$t be concerned if canvas adds a 'flag' $-1,-2,$dots for repeated

submissions$).$

compile with the command 'javac Project $1.$java'.

run using the command 'java Project l$\text{'}.$

accept input from a file called input.txt in the same directory as the java file$($s$)$ formatted precisely

as described above.

accomplishes the goal of the project. In other words, the output should be the correct answer

formatted correctly.

be submitted on time $($early and multiple times is fine$).$

For each listed item you fail to follow, expect to lose at least $5$ points. However, submitting via email will

guarantee you a zero.

Examples: Your program should work on any valid input and not just on the following examples. In

particular, I am very likely to test it on much larger inputs $($eg $N=50$ or even $N=100).$ While working

on the code you may want to print out extraneous information to help you debug. but delete such output

before your final submission. There are multiple possible ways to solve the problem. Any reasonable,

polynomial time method is permitted.