def check_input(l, n):
    nl = len(l)
    if nl != n:
        return False
    test = [0] * n
    for i in l:
        if i > n - 1 or i < 0:
            return False
        test[i] += 1
        if test[i] > 1:
            return False
    return True

print("----------Задача о марьяже----------")
n = int(input("Введите количество мужчин и женщин n: "))

m = []    # Wish list for every man
print("Введите предпочтения мужчин в порядке убывания (1 2 ... n)")
for i in range(n):
    f = False
    while not f:
        tmp = [int(x) - 1 for x in input(f"Предпочтения {i + 1}-го мужчины: ").split()]
        f = check_input(tmp, n)
        if not f:
            print("Некорректный ввод. Необходимо ввести разные числа от 1 до n.")
    m.append(tmp)

w = []    # Wish list for every woman
print("Введите предпочтения женщин в порядке убывания (1 2...n)")
for i in range(n):
    f = False
    while not f:
        tmp = [int(x) - 1 for x in input(f"Предпочтения {i + 1}-й женщины: ").split()]
        f = check_input(tmp, n)
        if not f:
            print("Некорректный ввод. Необходимо ввести разные числа от 1 до n.")
    w.append(tmp)

free_men = [x for x in range(n)]    # List of free men
women_hus = [-1] * n    # List of pairs. Index = woman idx, Value = man idx or -1 if she is free

while len(free_men) > 0:    # While free man exists
    tmp = free_men.copy()    # Temporary list because need to change len(free_men)
    for m_idx in tmp:
        w_idx = m[m_idx][0]    # The best woman for m_idx
        cur = women_hus[w_idx]    # Current man for w_idx

        if cur == -1:    # She is free
            women_hus[w_idx] = m_idx    # m_idx - man for w_idx
            free_men.remove(m_idx)     # Remove m_idx from free men
        elif w[w_idx].index(m_idx) < w[w_idx].index(cur):    # Her current man worse than m_idx
            women_hus[w_idx] = m_idx    # m_idx - man for w_idx
            free_men.remove(m_idx)    # m_idx not free
            free_men.append(cur)    # Current man becomes free
            m[cur].remove(w_idx)    # Remove w_idx from current man wish list
        else:    # Her current man better than m_idx
            m[m_idx].remove(w_idx)    # Remove w_idx from m_idx wish list

print('--------------------')
print("Получившиеся пары (m, w):")
for i in range(n):
    print(f'{i + 1}: ({women_hus[i] + 1}, {i + 1})')