in java Write a program that solves the classic $$stable marriage$$ problem. This problem deals with a group of men and a group of women.

$*$ The program tries to pair them up so as to generate as many stable marriages as possible. A set of marriages is unstable if

$*$ you can find a man and a woman who would rather be married to each other than to their current spouses $($in which 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 blank line, followed by all of the women, one per line. The men and women are numbered according to their

$*$ positions in the input file $($the first man is #$1,$ the second man is #$2,$ and so on; the first woman is #$1,$ the second woman is #$2,$

$*$ and so on$).$ Each input line $($except for the blank line separating men from women$)$ lists the person$$s name, followed by a colon,

$*$ followed by a list of integers. These integers are the marriage partner preferences of this particular person. For example, see

$*$ the following input line in the men$$s section: This line indicates that the person is named $$Joe$$ and that his first choice for

$*$ marriage is woman #$10,$ his second choice is woman #$8,$ and so on$.$ Any women not listed are considered unacceptable to Joe.

$*$ Joe: $108359202233629732161825$ The stable marriage problem is solved by the following algorithm: assign each person to be free.

while $($some man M with a nonempty preference list is free$)\{$

W $=$ first woman on M$\text{'}$s list.

if $($some man P is engaged to W$)\{$

assign P to be free.

$\}$

$*$ assign M and W to be engaged to each other.

for $($each successor Q of M who is on W$\text{'}$s list$)\{$

delete W from Q$\text{'}$s preference list.

delete Q from W$\text{'}$s preference list.

$\}$

$\}$

$*$ Consider the following input:

Man $1$: $4123$

Man $2$: $2314$

Man $3$: $2431$

Man $4$: $3142$

Woman $1$: $4132$

Woman $2$: $1324$

Woman $3$: $1234$

Woman $4$: $4132$

$*$ The following is a stable marriage solution for this input:

Man $1$ and Woman $4$

Man $3$ and Woman $2$

Man $2$ and Woman $3$

Man $4$ and Woman $1$

$*/$