This is the code for Gale$-$Shapley algorithm which handle cases where the number of men and women are unequal.

for this input case

$43$

m$1$ w$1$ w$2$ w$3$

m$2$ w$1$ w$3$ w$2$

m$3$ w$2$ w$1$ w$3$

m$4$ w$3$ w$1$ w$2$

w$1$ m$1$ m$2$ m$3$ m$4$

w$2$ m$3$ m$4$ m$1$ m$2$

w$3$ m$2$ m$1$ m$4$ m$3$

output not coming properly.

output came:

m$1$ w$1$

m$3$ w$2$

m$4$ w$3$

expected output:

m$1$ w$1$

m$2$ w$3$

m$3$ w$2$

please correct the logic of the algorithm.

Also provide psuedo code, time complexity and space complexity.

I want correct output for all test cases and here my code is failing so make sure it does not fail other test cases.