"""
Stable marriage problem in CPMpy.

From http://mathworld.wolfram.com/StableMarriageProblem.html
'''
Given a set of n men and n women, marry them off in pairs after each man has ranked the
women in order of preference from 1 to n, {w_1,...,w_n} and each women has done likewise,
{m_1,...,m_n}. If the resulting set of marriages contains no pairs of the form
{m_i,w_j}, {m_k,w_l} such that m_i prefers w_l to w_j and w_l prefers m_i to m_k,
the marriage is said to be stable. Gale and Shapley (1962) showed that a stable marriage exists
for any choice of rankings (Skiena 1990, p. 245).
In the United States, the algorithm of Gale and Shapley (1962) is used to match hospitals to
medical interns (Skiena 1990, p. 245). 
'''

Translation of the OPL version (via MiniZinc) from
Pascal Van Hentenryck "The OPL Optimization Programming Language"
E.g.
http://www.comp.rgu.ac.uk/staff/ha/ZCSP/additional_problems/stable_marriage/stable_marriage.pdf

Thanks to Tias Guns for getting the implications correct.

This CPMpy model was written by Hakan Kjellerstrand (hakank@gmail.com)
See also my CPMpy page: http://hakank.org/cpmpy/
"""
import math, sys
import numpy as np
from cpmpy import *
from cpmpy.solvers import *
import sys


def print_function(a):
    print("wife:", a[0].value())
    print("husband:", a[1].value())
  

def stable_marriage(problem,num_sols=0,num_procs=1):

    #
    # We must use cparray to be able to use element constraint.
    #
    rankMen = cparray(problem["rankMen"])
    print("rankMen:\n", rankMen)
    rankWomen = cparray(problem["rankWomen"])
    print("rankWomen:\n", rankWomen)
    n = len(rankMen)

    wife = intvar(0,n, shape=n,name="wife")
    husband = intvar(0,n, shape=n,name="husband")

    model = Model()
    model += [wife[husband[w]] == w for w in range(n)]
    model += [husband[wife[m]] == m for m in range(n)]
  
    for w in range(n):
      model += [(rankWomen[w,o] < rankWomen[w,husband[w]]).implies\
                (rankMen[o,wife[o]] < rankMen[o,w]) for o in range(n)]
    for m in range(n):
      model += [(rankMen[m,o] < rankMen[m, wife[m]]).implies\
                (rankWomen[o,husband[o]] < rankWomen[o,m]) for o in range(n)]

    def print_sol():
        print("wife   :", wife.value())
        print("husband:", husband.value())
        print()

    ss = CPM_minizinc(model,"gecode")
    num_solutions = ss.solveAll(display=print_sol)
    print("num_solutions:", num_solutions)



#
# Some problem instances.
# 
problems = {
  # Original problem from Van Hentenryck
 "van_hentenryck": {
    "rankWomen": [
        [1, 2, 4, 3, 5],
        [3, 5, 1, 2, 4],
        [5, 4, 2, 1, 3],
        [1, 3, 5, 4, 2],
        [4, 2, 3, 5, 1]
    ],

    "rankMen": [
        [5, 1, 2, 4, 3],
        [4, 1, 3, 2, 5],
        [5, 3, 2, 4, 1],
        [1, 5, 4, 3, 2],
        [4, 3, 2, 1, 5]
    ]
    },
 # From http://mathworld.wolfram.com/StableMarriageProblem.html
 "mathword": {
  "rankMen": [[7, 3, 8, 9, 6, 4, 2, 1, 5],
              [5, 4, 8, 3, 1, 2, 6, 7, 9],
              [4, 8, 3, 9, 7, 5, 6, 1, 2],
              [9, 7, 4, 2, 5, 8, 3, 1, 6],
              [2, 6, 4, 9, 8, 7, 5, 1, 3],
              [2, 7, 8, 6, 5, 3, 4, 1, 9],
              [1, 6, 2, 3, 8, 5, 4, 9, 7],
              [5, 6, 9, 1, 2, 8, 4, 3, 7],
              [6, 1, 4, 7, 5, 8, 3, 9, 2]],

 "rankWomen" : [[3, 1, 5, 2, 8, 7, 6, 9, 4],
                [9, 4, 8, 1, 7, 6, 3, 2, 5],
                [3, 1, 8, 9, 5, 4, 2, 6, 7],
                [8, 7, 5, 3, 2, 6, 4, 9, 1],
                [6, 9, 2, 5, 1, 4, 7, 3, 8],
                [2, 4, 5, 1, 6, 8, 3, 9, 7],
                [9, 3, 8, 2, 7, 5, 4, 6, 1],
                [6, 3, 2, 1, 8, 4, 5, 9, 7],
                [8, 2, 6, 4, 9, 1, 3, 7, 5]]
  },
  # Random 20x20 instances
  # http://hakank.org/minizinc/stable_marriage_random20.dzn 
  "random 20" : {
    "rankMen":[
             [10,4,3,20,19,11,2,18,6,13,17,5,7,12,14,16,8,15,9,1],
             [4,18,13,11,8,19,2,17,15,10,12,9,16,5,6,20,14,7,3,1],
             [14,11,13,4,17,10,6,12,16,2,7,1,19,9,20,5,3,15,8,18],
             [1,12,19,2,10,11,6,20,17,18,14,15,9,7,16,3,5,8,13,4],
             [8,2,12,20,5,10,9,15,7,16,6,13,18,1,11,14,4,19,3,17],
             [1,11,16,18,15,2,8,20,17,13,14,6,19,9,12,4,5,10,7,3],
             [6,5,20,13,10,1,4,9,17,15,12,14,3,16,18,19,8,2,11,7],
             [9,20,8,16,18,19,15,10,5,7,14,6,17,12,4,1,3,2,13,11],
             [2,20,10,8,14,5,18,15,1,17,16,9,4,6,11,3,19,12,13,7],
             [11,5,15,14,16,8,17,1,3,10,4,20,7,18,2,19,6,12,13,9],
             [11,10,8,13,5,3,15,2,9,1,7,12,14,17,6,19,16,20,4,18],
             [5,18,4,14,16,6,15,12,8,17,19,10,2,20,9,3,13,7,1,11],
             [3,17,14,9,10,16,11,13,8,1,2,6,5,18,4,20,15,19,7,12],
             [19,17,9,14,5,6,1,13,4,7,12,15,18,11,8,3,10,20,2,16],
             [12,5,6,14,16,4,18,3,11,19,15,17,2,13,1,8,9,20,7,10],
             [10,19,12,13,3,20,17,11,4,18,8,2,7,6,5,1,9,14,16,15],
             [2,19,1,12,16,20,6,13,14,11,18,17,4,10,9,5,3,15,7,8],
             [4,2,11,9,1,19,13,17,6,15,18,8,10,16,12,3,14,5,7,20],
             [18,17,8,4,10,13,19,1,12,20,3,11,5,7,6,14,15,9,2,16],
             [11,1,12,16,7,15,3,18,5,8,13,19,6,4,9,20,2,14,10,17]
             ],
   "rankWomen" : [
             [14,13,1,18,12,10,16,19,20,11,2,8,15,3,6,17,5,4,9,7],
             [1,7,13,3,18,16,17,20,9,6,2,11,14,10,4,8,12,19,15,5],
             [9,20,5,10,2,3,14,16,11,4,15,6,13,18,17,8,1,12,7,19],
             [3,7,1,11,8,13,18,20,12,16,2,4,15,9,10,17,6,19,14,5],
             [2,4,13,9,7,14,1,20,15,19,18,5,17,11,6,8,16,3,12,10],
             [12,16,4,15,9,14,17,6,2,1,7,11,8,10,19,20,13,18,3,5],
             [16,12,20,19,14,17,10,2,13,5,1,6,18,11,15,7,4,9,8,3],
             [2,15,1,20,10,19,7,14,6,8,16,9,18,4,5,12,17,11,3,13],
             [15,18,12,9,2,19,17,4,13,5,6,8,16,1,7,14,20,3,11,10],
             [12,1,7,18,17,4,14,15,5,8,10,20,19,16,2,9,13,6,3,11],
             [12,2,18,11,16,19,8,4,15,10,9,20,1,7,5,6,13,14,17,3],
             [14,15,11,7,16,12,2,1,17,4,20,3,5,9,8,18,13,19,6,10],
             [19,10,15,7,16,9,4,18,17,12,2,8,1,13,20,6,5,3,11,14],
             [13,2,12,3,19,6,16,5,7,9,11,4,1,18,20,14,8,10,17,15],
             [3,12,17,14,4,10,20,15,5,9,19,16,8,7,13,6,1,2,11,18],
             [16,20,2,10,17,11,9,8,15,12,13,5,14,4,7,3,18,19,1,6],
             [12,11,10,6,19,1,4,2,8,20,15,3,13,9,18,14,17,16,5,7],
             [16,7,1,13,11,3,8,2,9,14,10,6,15,17,20,12,18,4,5,19],
             [11,9,2,7,13,5,16,14,1,12,19,15,8,4,20,6,17,10,3,18],
             [6,15,3,19,8,9,5,1,11,7,12,18,13,4,10,16,17,14,20,2]
             ]
   },
   #
   # http://hakank.org/minizinc/stable_marriage_random50.dzn
   # 50x50
   "random50x50":  {
      "rankMen": [
  [35,39,42,37,1,22,7,3,8,15,23,47,31,6,43,40,10,50,48,14,44,28,16,45,26,34,24,20,32,49,11,5,36,19,17,29,41,4,38,25,18,13,9,21,33,12,46,2,30,27],
[33,8,1,22,39,12,49,41,48,23,10,6,35,40,26,38,43,2,50,37,4,44,34,32,31,18,7,42,19,5,45,29,46,16,11,28,36,14,21,15,17,9,47,13,27,24,30,25,20,3],
[18,14,32,33,23,35,16,43,26,17,48,21,12,46,3,50,49,25,34,42,27,6,11,29,4,41,8,37,22,47,9,28,39,13,7,36,30,31,24,20,2,10,1,15,45,40,19,5,38,44],
[3,25,21,28,41,36,48,46,10,2,19,35,14,13,11,37,33,20,5,50,4,27,22,7,12,39,26,43,34,1,24,38,32,29,49,15,17,18,16,9,31,8,30,42,23,44,6,45,40,47],
[8,23,18,34,25,21,20,16,11,2,47,6,32,43,3,22,50,36,26,42,10,5,39,30,15,45,44,19,48,1,12,37,29,49,24,41,13,9,33,7,27,40,38,28,35,17,46,14,4,31],
[35,26,42,17,27,12,5,1,4,24,15,38,14,31,9,32,6,50,28,39,49,13,16,43,45,36,41,3,23,10,29,33,22,8,30,11,21,19,25,20,18,2,40,46,48,34,44,7,37,47],
[14,26,18,29,48,8,15,20,41,1,11,12,7,45,22,10,46,16,31,38,3,13,5,40,36,23,2,30,50,43,17,24,4,37,42,32,25,6,19,49,28,21,33,39,34,47,35,27,9,44],
[32,33,39,20,4,37,8,47,1,10,36,12,43,49,22,29,46,14,11,48,50,6,31,25,2,13,23,19,40,28,3,18,9,41,44,16,21,7,35,45,38,24,17,42,15,34,26,30,27,5],
[25,39,40,7,11,36,29,31,27,17,49,32,12,37,19,43,34,8,18,2,10,48,16,3,46,9,30,15,20,44,22,28,47,4,38,42,13,26,5,1,6,23,24,21,35,50,41,14,45,33],
[42,25,9,40,10,36,48,1,28,13,16,24,6,49,45,50,33,23,19,4,2,17,47,7,11,35,34,26,44,43,18,12,29,8,32,15,3,5,21,14,41,30,39,31,38,27,46,37,20,22],
[29,44,9,33,49,46,38,18,12,41,1,32,30,19,39,50,27,11,21,31,37,17,22,16,14,15,13,47,20,26,42,43,3,40,23,24,25,45,28,10,5,8,4,2,6,48,7,35,34,36],
[19,48,50,36,8,38,4,24,31,30,29,17,2,1,7,3,47,41,23,37,43,5,33,10,44,49,34,22,14,9,6,27,26,16,18,20,13,40,21,15,39,28,25,11,45,42,46,32,12,35],
[49,23,20,46,8,9,31,41,26,3,24,30,13,11,47,28,17,36,40,44,2,12,10,35,27,7,19,5,37,22,39,1,15,25,33,38,48,50,21,43,4,42,14,6,45,32,34,29,16,18],
[47,48,49,45,18,38,17,36,37,1,6,27,34,25,12,15,4,33,39,13,7,2,41,10,31,30,11,14,26,9,21,5,35,8,24,3,44,29,23,20,16,46,32,43,42,50,40,19,22,28],
[50,33,5,31,44,46,4,40,42,29,10,26,30,7,1,17,6,8,45,21,34,39,13,35,12,11,48,32,3,47,19,27,41,49,25,36,23,22,18,14,9,37,43,20,16,24,28,15,2,38],
[2,47,22,31,17,3,10,14,25,12,11,7,35,30,4,49,23,44,50,48,41,34,38,6,19,33,27,26,32,20,16,37,21,45,5,29,43,28,13,46,42,39,36,8,40,18,24,9,1,15],
[27,2,35,15,25,46,50,31,34,48,4,21,33,22,38,12,5,20,16,39,9,6,32,18,26,24,40,1,41,36,8,29,49,44,37,17,30,45,7,13,47,3,10,11,28,14,23,42,43,19],
[13,44,38,14,22,26,20,33,19,17,23,24,8,6,12,34,31,16,45,15,39,40,50,27,36,4,42,2,28,43,9,29,1,11,49,37,48,35,3,5,10,41,46,7,30,21,25,32,18,47],
[15,38,23,49,16,37,17,33,47,44,20,31,45,1,6,29,14,46,48,13,41,9,8,5,19,42,7,26,12,50,43,39,22,18,27,32,34,10,21,11,24,3,4,2,35,28,30,25,40,36],
[16,21,20,12,45,27,47,17,29,24,9,49,48,36,42,39,4,38,46,23,7,30,44,8,19,10,5,15,43,40,33,11,34,28,32,35,25,37,41,22,1,14,6,3,50,2,13,26,18,31],
[47,41,35,17,10,9,5,28,48,4,24,50,29,14,42,32,20,44,16,27,33,11,3,46,13,49,23,12,39,31,36,19,26,15,7,37,45,2,21,38,8,22,6,18,30,34,43,1,25,40],
[1,9,30,40,50,46,15,13,48,25,31,19,24,12,36,41,22,43,45,42,6,18,28,33,2,5,39,38,8,32,34,4,11,37,3,16,29,47,14,17,7,10,20,44,21,23,27,26,49,35],
[7,11,36,19,37,47,5,2,49,50,35,39,12,13,4,15,8,10,18,25,29,20,30,3,21,33,40,14,23,17,28,16,43,48,44,9,1,41,32,45,27,38,42,6,46,34,26,22,24,31],
[22,12,18,17,50,33,2,16,34,10,1,44,23,19,32,47,38,20,8,45,29,27,26,30,42,13,7,21,15,43,37,24,25,48,9,49,36,35,41,39,14,6,11,28,31,46,5,40,3,4],
[29,48,47,3,28,4,8,1,30,35,43,49,36,24,46,21,10,2,14,16,41,20,45,7,26,12,32,27,39,17,23,31,25,42,18,34,13,44,11,15,6,50,37,40,19,9,22,33,38,5],
[44,31,30,3,47,10,15,24,19,39,9,2,45,28,43,33,49,48,41,42,23,17,38,1,29,13,11,37,22,40,18,20,34,35,4,21,27,12,36,8,14,5,46,26,16,32,50,6,25,7],
[26,40,42,28,3,37,36,6,20,46,11,48,8,27,24,45,7,14,32,16,35,43,17,15,13,23,31,47,10,39,21,12,1,49,44,9,5,4,29,38,2,22,18,34,50,41,25,19,33,30],
[24,10,17,38,43,6,8,18,28,11,7,31,14,39,32,19,26,22,16,27,3,29,9,20,4,35,30,2,40,42,15,36,45,46,48,23,49,12,1,21,5,50,33,41,47,37,25,34,44,13],
[12,31,17,45,26,4,27,41,16,7,44,35,32,25,11,38,18,24,42,46,29,33,20,10,13,40,48,30,36,43,15,2,6,8,3,5,9,34,19,14,21,50,23,39,49,47,22,37,1,28],
[34,43,40,13,46,6,37,10,16,47,11,9,36,41,29,28,45,26,21,33,3,31,8,38,1,48,49,12,2,4,50,39,20,7,25,44,27,35,19,30,15,18,5,42,24,17,22,14,23,32],
[28,20,37,29,7,8,17,18,10,48,49,21,12,33,26,36,5,1,30,45,40,47,14,25,31,15,39,16,4,3,44,11,46,35,24,41,42,32,27,50,9,43,22,34,6,19,13,23,2,38],
[41,6,17,3,30,34,47,7,29,8,37,25,39,28,48,40,15,50,49,13,32,42,38,1,21,16,5,26,36,45,23,12,19,22,24,44,4,2,33,10,43,9,14,46,27,18,11,31,20,35],
[23,36,44,9,32,49,12,40,21,33,20,8,28,17,2,3,14,39,26,25,35,19,16,5,30,13,18,37,31,24,6,45,10,1,27,48,7,15,50,46,22,42,11,47,29,4,43,41,38,34],
[39,50,11,22,43,6,20,46,17,3,49,48,10,16,13,1,25,9,23,14,21,28,19,30,27,38,2,26,34,40,45,35,8,5,37,32,24,42,31,47,44,36,12,7,29,4,33,41,15,18],
[40,28,47,7,24,35,36,19,22,30,34,8,11,10,26,23,13,46,49,14,3,6,33,4,44,9,12,1,21,27,31,18,29,38,16,17,37,39,43,32,45,15,25,50,20,5,42,41,48,2],
[33,28,46,17,37,2,8,27,11,20,15,24,29,36,25,7,31,38,34,23,32,4,45,3,6,12,44,19,10,9,43,48,26,50,30,13,49,47,14,42,5,40,39,1,22,21,41,35,18,16],
[46,37,15,29,2,36,9,26,12,38,34,44,25,28,5,39,19,16,33,17,8,50,45,1,42,23,7,21,10,14,27,43,31,24,4,49,22,30,48,35,11,32,13,18,3,6,20,41,40,47],
[47,6,39,45,3,33,43,19,48,21,22,37,20,25,17,35,36,14,24,5,44,30,50,26,46,16,9,2,32,10,31,23,11,7,12,28,29,40,4,18,1,42,38,34,13,8,41,49,15,27],
[30,36,26,50,7,15,6,35,9,11,34,48,39,3,21,12,13,22,25,43,29,2,31,24,40,16,49,4,18,32,28,42,17,37,1,10,46,44,41,45,14,8,20,27,47,33,19,38,23,5],
[28,36,43,17,35,8,1,49,2,38,26,19,12,5,31,44,21,13,7,18,46,30,37,22,41,11,42,27,48,33,25,23,45,32,40,4,10,47,39,6,16,34,3,15,24,9,14,20,50,29],
[18,13,30,46,27,12,5,43,40,16,38,37,24,22,34,9,29,7,28,4,10,25,32,1,3,20,26,47,44,6,2,17,48,14,33,42,49,45,21,36,39,35,50,15,19,8,41,31,11,23],
[25,33,2,9,23,11,48,50,35,44,17,18,10,24,38,20,28,19,22,49,47,46,34,27,36,16,4,8,42,37,21,6,41,45,14,39,29,5,15,31,43,12,26,40,3,13,1,32,7,30],
[45,11,36,25,29,43,16,42,4,26,30,7,17,35,12,49,14,9,8,39,24,19,13,3,18,32,27,31,33,21,20,40,10,15,47,34,2,5,1,37,41,23,6,46,50,28,22,38,48,44],
[31,19,32,28,27,39,9,14,2,15,36,40,20,23,8,11,12,46,43,13,47,16,48,33,18,29,25,3,24,21,50,45,37,44,22,10,17,34,6,7,5,26,42,30,4,49,1,35,41,38],
[21,26,43,2,6,18,47,39,48,36,14,17,16,49,12,33,15,38,25,7,40,4,42,45,20,10,28,50,1,5,8,9,32,30,27,22,23,35,19,44,37,3,34,24,41,31,13,29,46,11],
[5,8,48,33,31,28,34,43,26,39,3,49,21,35,46,36,41,1,38,6,2,25,4,12,18,14,20,15,37,7,45,44,23,17,10,24,11,47,9,30,27,22,13,29,40,42,16,19,32,50],
[12,9,41,19,38,32,39,49,46,23,48,21,13,45,22,31,4,26,34,29,14,25,2,15,43,50,42,11,33,40,5,27,35,37,28,20,30,18,24,47,6,8,36,7,3,16,1,17,10,44],
[43,22,41,39,45,49,50,7,21,25,23,14,32,18,5,46,2,48,29,38,26,31,8,34,19,13,3,9,42,4,37,28,27,24,36,1,15,12,10,16,40,47,20,33,30,6,35,44,11,17],
[46,34,48,14,49,7,43,45,10,23,21,42,3,44,18,8,50,39,25,38,30,13,26,32,33,2,29,37,40,15,41,22,35,20,47,6,1,36,28,24,9,4,12,27,31,19,16,17,5,11],
[47,11,43,44,37,25,19,29,40,23,3,50,20,22,39,28,15,36,5,9,49,34,38,27,24,48,32,41,13,14,30,26,1,8,6,2,18,21,4,42,17,35,7,10,12,31,33,16,45,46]
],
     "rankWomen": [
  [11,12,45,2,43,5,4,42,29,19,32,7,47,18,31,50,14,46,16,39,22,8,37,35,38,41,20,40,9,24,23,1,21,26,25,13,15,48,27,10,33,30,3,34,36,44,28,49,17,6],
[36,35,33,1,32,13,40,9,12,44,38,45,42,23,46,50,21,8,28,26,11,3,6,18,19,43,25,29,47,34,37,14,16,7,15,39,31,22,27,17,2,10,41,48,5,30,49,24,20,4],
[37,22,45,10,33,38,35,4,50,43,20,24,25,21,31,40,12,48,5,1,15,7,26,28,47,46,6,30,44,39,42,17,36,49,11,3,13,16,34,27,41,8,19,29,23,9,14,2,18,32],
[31,7,21,8,13,49,3,32,25,30,6,9,22,43,11,1,35,20,24,47,12,38,42,18,44,28,27,36,29,14,39,5,48,17,50,19,45,2,41,34,10,4,15,40,26,37,46,16,23,33],
[20,36,22,50,8,33,18,16,3,21,35,11,13,42,27,38,15,37,25,45,30,1,26,9,31,23,39,7,41,28,46,40,48,5,24,32,49,44,4,34,43,12,29,6,14,10,19,47,17,2],
[45,3,10,29,35,42,2,7,36,16,23,33,13,4,38,15,50,43,30,27,9,31,37,14,21,28,49,22,1,19,11,34,5,26,41,40,32,24,47,12,46,18,17,39,20,44,25,6,8,48],
[44,2,17,38,22,27,35,48,24,5,50,8,1,15,49,37,46,19,10,26,33,43,11,42,30,32,39,34,25,40,20,41,28,18,3,13,9,23,36,45,6,4,16,29,31,12,14,47,21,7],
[8,10,34,45,47,16,22,50,28,2,49,4,37,7,24,29,3,44,35,5,11,26,27,30,33,38,17,13,43,48,21,25,15,31,41,32,9,46,12,39,6,18,42,36,1,40,19,20,14,23],
[37,5,10,46,14,4,42,19,32,40,12,13,43,25,50,2,23,26,28,41,49,35,45,48,36,21,31,30,44,8,39,24,9,27,33,3,11,47,15,7,22,16,17,6,1,20,29,18,34,38],
[41,43,31,27,35,15,5,48,29,13,40,28,42,22,20,17,14,30,44,7,3,37,9,25,45,21,8,39,19,24,34,38,49,50,46,47,33,32,4,23,11,18,1,6,26,10,12,2,16,36],
[38,44,50,25,29,36,39,42,33,22,9,16,26,28,23,8,45,10,41,3,14,18,13,48,34,37,7,32,15,46,47,21,4,1,27,30,43,24,6,17,5,12,40,35,31,19,20,11,2,49],
[43,33,12,31,35,34,3,19,44,14,50,24,1,30,8,32,28,13,15,11,10,38,18,26,29,39,46,40,25,37,17,36,42,6,48,5,49,4,16,7,27,2,22,45,41,20,21,47,9,23],
[31,43,27,40,41,44,5,17,36,39,34,30,32,3,47,42,50,7,8,38,20,23,25,28,29,49,26,11,45,13,9,19,35,6,2,1,46,16,48,37,10,24,33,15,12,21,4,22,14,18],
[8,12,14,38,29,37,19,16,7,47,33,31,9,17,1,30,40,23,50,2,49,4,13,43,41,10,11,24,5,42,27,25,35,36,18,22,45,44,46,32,15,26,28,39,34,48,20,6,21,3],
[30,46,24,9,4,13,2,31,35,48,12,11,25,36,1,33,40,22,7,28,47,21,27,50,45,34,10,19,3,29,6,38,39,44,20,41,5,8,14,26,23,37,32,42,18,49,17,15,43,16],
[25,24,3,27,5,17,36,29,23,39,34,42,12,45,31,16,19,20,8,21,26,2,22,37,46,49,18,1,9,44,33,11,14,48,13,4,32,15,41,35,30,6,7,28,43,10,47,38,50,40],
[27,6,18,25,9,2,20,22,45,21,32,29,26,15,34,44,4,14,37,11,16,31,8,41,5,7,10,19,33,28,46,24,30,43,50,38,17,48,35,39,42,13,36,40,3,47,1,12,23,49],
[28,6,32,29,23,47,27,40,44,43,2,19,48,49,31,37,21,4,38,15,50,30,17,14,46,3,24,1,10,11,41,25,12,7,42,33,34,8,20,22,39,36,26,35,13,18,45,9,16,5],
[31,2,37,3,14,30,49,42,25,38,17,35,43,24,8,41,7,23,16,40,11,48,4,44,22,12,27,26,32,10,21,47,13,33,45,19,46,50,18,28,9,39,20,6,29,36,15,5,1,34],
[18,14,17,27,1,8,49,6,10,42,43,30,11,50,37,46,35,12,31,25,28,20,32,21,3,45,33,7,26,19,38,47,40,4,44,39,29,13,41,16,24,15,9,48,22,34,36,2,23,5],
[22,20,4,43,39,16,37,44,2,50,7,3,15,34,35,23,27,38,48,25,32,13,19,30,46,1,21,42,31,12,10,41,6,28,11,47,29,17,5,14,26,45,40,49,18,33,24,36,8,9],
[29,46,37,5,26,42,45,10,30,23,13,4,39,50,14,15,49,31,22,34,20,48,43,33,28,41,17,25,8,47,12,24,38,44,7,36,3,16,40,9,19,2,11,21,6,18,1,35,27,32],
[22,20,41,18,25,17,38,24,1,40,16,39,49,3,13,14,19,6,35,23,26,29,43,27,7,9,44,28,11,46,12,48,21,37,30,8,33,34,36,47,10,31,15,42,32,45,2,4,50,5],
[29,36,47,10,12,34,49,39,22,4,14,37,19,41,21,33,26,16,20,3,30,23,6,32,17,11,9,15,46,43,40,38,18,35,24,44,2,8,50,28,48,1,42,45,25,7,27,5,31,13],
[31,29,18,15,26,32,42,48,14,34,10,27,50,30,1,44,46,3,23,6,20,24,8,13,2,45,5,37,4,40,9,17,28,11,25,16,39,36,12,47,7,22,33,35,38,21,41,19,43,49],
[14,45,42,38,44,30,41,29,26,39,34,32,21,6,46,49,11,22,15,23,10,33,2,20,8,7,5,16,43,3,4,36,50,13,12,18,31,28,48,25,47,24,35,40,27,37,9,1,17,19],
[19,17,2,30,44,12,46,20,24,40,28,7,9,29,8,5,33,26,18,39,1,27,3,6,48,31,35,49,32,11,42,10,45,41,22,14,15,47,43,34,25,13,36,4,21,23,37,50,38,16],
[49,44,10,37,6,3,16,32,45,26,31,14,11,5,20,1,8,18,15,27,21,25,50,7,38,2,42,46,24,23,34,48,35,29,22,30,36,19,39,47,41,33,28,4,43,17,13,9,40,12],
[13,14,26,19,11,4,29,28,18,10,32,47,45,33,8,40,41,37,39,9,17,24,2,38,42,16,25,5,48,22,50,35,6,1,12,44,43,23,31,7,36,34,27,49,30,21,46,15,20,3],
[49,33,11,47,38,7,41,28,27,2,32,1,24,21,5,4,43,22,37,36,23,8,13,34,30,9,3,18,39,29,44,35,31,14,46,10,26,16,25,15,6,40,48,19,17,42,20,45,50,12],
[2,36,44,6,23,31,1,16,25,42,45,15,47,5,49,34,38,19,11,10,48,12,43,30,40,27,17,32,20,24,26,50,29,28,41,18,7,39,3,21,37,8,35,46,9,22,13,14,4,33],
[42,29,32,28,38,21,30,13,17,11,20,44,50,27,41,1,19,35,36,16,15,7,22,47,33,37,39,25,48,9,23,45,12,18,14,43,46,24,8,49,10,4,26,3,40,2,6,31,5,34],
[15,48,50,43,20,16,33,36,42,26,39,6,19,18,1,13,5,22,31,34,25,2,8,21,38,3,12,41,35,30,28,17,29,23,46,44,11,27,47,7,9,14,49,24,40,45,32,37,4,10],
[32,11,16,4,37,28,5,19,13,40,15,49,23,39,35,41,26,7,2,44,48,1,50,43,17,14,25,36,29,21,47,31,27,20,46,6,10,12,8,9,33,3,24,42,22,30,34,18,45,38],
[11,19,10,15,35,48,6,44,20,16,21,27,8,1,13,22,30,25,4,32,39,36,42,41,12,49,28,24,34,14,17,38,47,5,37,7,46,43,23,29,26,33,9,50,18,2,45,31,40,3],
[1,21,43,14,27,49,15,18,2,4,42,41,6,19,38,26,31,30,47,20,16,24,37,22,28,8,48,13,40,29,17,23,25,45,39,46,44,5,9,11,10,33,50,36,3,34,32,35,7,12],
[41,18,15,7,50,44,33,45,20,6,40,34,29,19,14,4,35,31,38,2,3,1,27,13,23,48,11,9,30,21,5,10,16,43,17,24,49,25,39,12,28,47,26,8,22,37,32,42,36,46],
[39,14,43,2,33,21,17,27,26,47,13,30,4,35,32,18,1,24,11,25,28,46,34,48,23,19,5,31,40,15,44,16,37,36,45,3,7,20,42,50,22,12,9,41,10,38,29,49,8,6],
[14,18,16,44,31,23,38,5,24,7,25,49,47,30,36,20,45,28,15,26,8,4,34,17,39,48,46,11,22,37,32,3,50,43,21,13,33,10,41,1,19,12,6,42,2,9,29,27,35,40],
[37,42,44,30,8,26,43,31,40,5,18,45,36,28,14,22,41,33,27,38,29,34,6,16,10,39,35,15,19,9,4,23,2,3,24,11,47,17,46,25,1,12,32,48,50,7,20,13,21,49],
[14,47,48,23,2,39,43,34,3,22,45,27,17,41,35,9,20,26,10,7,46,44,29,5,19,40,49,30,37,6,12,11,42,1,24,18,16,50,8,33,36,25,31,32,38,28,15,13,4,21],
[39,42,23,15,9,17,47,5,29,14,36,33,11,43,45,30,10,6,50,28,16,25,26,35,34,7,3,20,12,8,18,13,44,22,27,49,21,37,38,31,2,24,46,4,32,48,19,41,40,1],
[22,41,23,40,6,48,37,45,30,7,49,1,35,47,21,34,9,13,29,17,18,16,14,24,15,42,12,31,33,36,46,2,44,50,28,11,39,38,43,19,27,4,5,32,8,3,25,20,10,26],
[31,8,23,34,5,11,50,46,47,27,49,29,42,24,20,15,40,36,43,7,38,22,9,45,13,33,19,41,16,10,28,32,12,48,4,30,2,18,1,44,21,17,35,39,37,14,6,25,3,26],
[23,11,25,42,20,34,9,7,48,37,5,4,32,47,2,19,41,29,17,21,30,24,44,10,36,46,6,39,14,28,3,33,27,38,1,35,31,40,18,43,45,8,50,49,12,22,15,26,13,16],
[9,26,43,35,17,33,16,13,37,44,21,31,32,38,11,15,46,36,49,14,8,3,27,23,28,12,45,4,34,20,39,7,2,42,50,5,40,24,29,48,19,1,30,41,10,47,6,18,25,22],
[32,19,24,1,30,14,33,49,36,23,25,6,8,31,13,45,34,20,29,26,4,38,21,41,47,37,15,9,22,11,27,10,46,44,35,2,5,18,48,3,40,16,42,50,39,12,7,17,43,28],
[34,16,13,9,11,47,25,35,4,30,32,15,10,2,1,7,38,48,29,21,49,14,40,44,28,18,33,6,12,36,23,46,45,19,50,17,22,3,24,27,42,43,26,31,5,20,8,37,39,41],
[24,45,18,46,19,8,41,31,29,42,11,7,48,13,39,26,28,3,22,47,44,35,32,20,4,34,33,2,37,50,5,12,30,15,43,36,27,17,6,25,23,14,9,1,38,21,10,16,40,49],
[50,43,33,36,28,37,21,13,1,16,15,32,23,24,19,2,17,26,30,18,6,40,10,46,34,38,42,29,39,22,45,20,25,5,27,9,31,14,44,11,12,47,8,3,7,4,48,35,49,41]
]
  },
 

}


# stable_marriage(van_hentenryck)
for p in problems:
  print(f"problem: {p}")
  stable_marriage(problems[p])
  print()