def solve():
    men_prefs = {
        'M1': ['W1', 'W2', 'W3'],
        'M2': ['W2', 'W1', 'W3'],
        'M3': ['W1', 'W2', 'W3']
    }

    women_prefs = {
        'W1': ['M2', 'M1', 'M3'],
        'W2': ['M1', 'M2', 'M3'],
        'W3': ['M1', 'M2', 'M3']
    }

    print(men_prefs)
    print(women_prefs)
    print()

    women_ranks = {w: {m: i for i, m in enumerate(prefs)} for w, prefs in women_prefs.items()}

    free_men = list(men_prefs.keys())
    engaged_pairs = {}
    proposal_index = {m: 0 for m in men_prefs}

    while free_men:
        man = free_men.pop(0)
        
        woman = men_prefs[man][proposal_index[man]]
        proposal_index[man] += 1

        if woman not in engaged_pairs:
            engaged_pairs[woman] = man
        else:
            current_fiance = engaged_pairs[woman]
            
            if women_ranks[woman][man] < women_ranks[woman][current_fiance]:
                engaged_pairs[woman] = man
            else:
                free_men.append(man)

    print("Stable Matching Results")
    final_matches = sorted([(m, w) for w, m in engaged_pairs.items()])
    for m, w in final_matches:
        print(f"{m} is matched with {w}")

if __name__ == "__main__":
    solve()