import sys

def solve():
    # Read all input data (fast IO pattern)
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    men_prefs = {}
    women_prefs = {}
    
    # State machine to parse the formatted textbook input
    state = None
    i = 0
    while i < len(input_data):
        token = input_data[i]
        if token == "Men" and i+1 < len(input_data) and input_data[i+1] == "Preferences:":
            state = "MEN"
            i += 2
            continue
        elif token == "Women" and i+1 < len(input_data) and input_data[i+1] == "Preferences:":
            state = "WOMEN"
            i += 2
            continue

        if token.endswith(":"):
            person = token[:-1]
            prefs = []
            i += 1
            while i < len(input_data) and not input_data[i].endswith(":") and input_data[i] not in ["Men", "Women"]:
                prefs.append(input_data[i])
                i += 1
            if state == "MEN":
                men_prefs[person] = prefs
            else:
                women_prefs[person] = prefs
            continue
        i += 1

    # Initialization for Gale-Shapley Algorithm
    free_men = list(men_prefs.keys())
    matches = {} # Maps woman -> current engaged man
    proposals = {m: 0 for m in men_prefs} # Tracks which woman a man should propose to next

    # Precompute women rankings for O(1) comparison (inverse preference arrays)
    women_ranks = {}
    for w, prefs in women_prefs.items():
        women_ranks[w] = {m: rank for rank, m in enumerate(prefs)}

    # Iterative improvement loop
    while free_men:
        m = free_men.pop(0)
        # Man gets the next woman on his list
        w = men_prefs[m][proposals[m]]
        proposals[m] += 1

        if w not in matches:
            # Woman is free, accepts proposal
            matches[w] = m
        else:
            m_prime = matches[w]
            # Lower rank index means higher preference
            if women_ranks[w][m] < women_ranks[w][m_prime]:
                matches[w] = m
                free_men.append(m_prime) # Previous fiance becomes free
            else:
                free_men.append(m) # Proposal rejected, man remains free

    print("Stable Matching:")
    # Sort output symmetrically 
    result = [(m, w) for w, m in matches.items()]
    result.sort()
    for m, w in result:
        print(f"{m} - {w}")

if __name__ == "__main__":
    solve()

"""
=== SAMPLE INPUT ===
Men Preferences:
M1: W1 W2 W3
M2: W2 W1 W3
M3: W1 W2 W3
Women Preferences:
W1: M2 M1 M3
W2: M1 M2 M3
W3: M1 M2 M3

=== SAMPLE OUTPUT ===
Stable Matching:
M1 - W1
M2 - W2
M3 - W3
"""