Use JAVA, In this project, you will implement a stack and use it to solve the stable marriage problem using backtracking. You are to explicitly use your stack to keep track of state in this implementation. Your program is to determine a pairing where there exist no two programmers that are not paired but would prefer each other to their actual partners.

In this project you will implement a stack and use it to solve the stable marriage problem using backtracking. We willaddress the stable marriage problem in class along with backtracking. You are to explicitly use your stack to keep track of state in this implementation. escription Details Input to this problem will come from a file. The file contains the number of pairings to make and two arrays indicating the preferences of each side. The input data will come from a file "ProjectiTestData.txt" and will be formatted as follows: number of pairings to make 4 Bobbie /First person's name in group A Bob's preferences (O highest) second person 's name in group A Ted Gina 3 2 10 Harry 0 2 13 Mel 3 2 10 Barb 2 130 olive 2 3 10 Sam 2 0 1 3 Your program is to determine a pairing where there exist no two programmers that are not paired but would prefer each other to their actual partners. Your output upon finding a suitable pairing should be a list of the team pairs. l First person's name in group B Mel's preferences cO-highest) Team 0: Gina and Mel Team 1: Harry and Sam Team 2: Bobbie and olive Team 3: Ted and Barb If no such pairing exists you should output the message: No stable pairing exists