= Stable Marriage Problem = <> == Problem Description == Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable". The stable marriage problem (SMP) is the problem of finding a stable matching mapping men to women. Stability in a matching requires that whenever there is no element A of the first matched set that prefers an element B (that it's not matched to) of the second matched set, and at the same time B also prefers A over the one B is matched with. SMP has several practical applications, as well as several variants. The variant proposed here is known to be polynomially solvable. == Input format == == Output format == == Example == == Author(s) == * Francesco Ricca * University of Calabria, Italy * Mario Alviano * University of Calabria, Italy * Marco Manna * University of Calabria, Italy == References == * D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962. * D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms, p. 54; MIT Press, 1989.