Stable Marriage Problem Objectives: Practice LinkedList You are going to write a program that solves a classic computer science problem known as the stable marriage problem. The input file is divided into men and women and the program tries to pair them so as to generate as many marriages as possible that are all stable. A set of marriages is unstable if yo can find a man and a woman who would rather be married to each other than to their spouses (in whic case, the two would be inclined to divorce their spouses and marry each other). The input file for the program will list all of the men, one per line, followed by a line with just the wor "END" on it, followed by all of the women, one per line, followed by another line with just the word "END" on it. The men and women are numbered by their position in the input file. To make this easi we assign numbers starting at 0 (the first man is #0, the second man is al, and so on; the first woman i #0, the second woman is #1, and so on). Each input line (except the two lines with "END') has a name followed by a colon followed by a list of integers. The integers are the preferences for this particular person. For example, the following input line in the men's section: Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24 indicates that the person is named "Joe" and that his first choice for marriage is woman #9, his second choice is woman a7, and so on. Any women not listed are considered unacceptable to Joe. The data fil has been purged of any impossible pa where one person is interested in the other, but the other considers that person unacceptable. Thus, ifa woman appears on Joe's list, then Joe is acceptable to tha There are many ways to approach the stable marriage problem. You are to implement a specific algorithm described below. This is the basic outline: set each person to be free; while (some man m with a nonempty preference list is free) first woman on m's list; if (some man p is engaged to w) setp to be free set mand w to be engaged to each other for (each successor q ofm on w's list) delete w from q's preference list delete qfrom w's preference list