#!/usr/local/bin/python

# Facebook programming puzzle
# Refrigerator Madness
#
# URL: http://tungwaiyip.info/blog/2010/02/22/refrigerator_madness_solution_facebook_programming_puzzle

from pprint import pprint as pp
import sys


def log(msg):
    print >>sys.stderr, '>>', msg


def load(filename):
    """
    Return list of engineer's list of drink preference.

    E.g.
      [[0, 2, 1], [1, 2, 0], [2, 1, 0], [1, 0, 2], [2, 0, 1], [0, 1, 2]]

    """
    data = []
    fp = open(filename)
    try:
        pcount, dcount = fp.readline().split()[:2]
        pcount = int(pcount)
        dcount = int(dcount)

        # ignore the drink list
        for i in xrange(dcount):
            line = fp.readline()

        for i in xrange(pcount):
            line = fp.readline()
            id, lst = line.split()
            lst = lst.strip().split(',')
            lst = map(int, lst)
            data.append(lst)
    finally:
        fp.close()

    return data


def calc_pref(A, B):
    """ Calc Facebook fridgemadness score """
    score = 0
    for i in xrange(len(A)):
        k = len(A) - i
        if i < len(B) and A[i] == B[i]:
            score += k*k
        elif A[i] not in B[:i]:
            score += k
    return score


def build_pref_matrix(data):
    """ Translate fridgemadness score into two list of list of ranked partners. """
    N = len(data)/2
    MP = []
    FP = []

    for m in xrange(N):
        mp = []
        for f in xrange(N):
            score = calc_pref(data[m], data[N+f])
            mp.append((score,f))
        mp = [id for score, id in sorted(mp,reverse=True)]
        MP.append(mp)

    for f in xrange(N):
        fp = []
        for m in xrange(N):
            score = calc_pref(data[N+f], data[m])
            fp.append((score,m))
        fp = [id for score, id in sorted(fp,reverse=True)]
        FP.append(fp)

    return MP, FP


#------------------------------------------------------------------------
# Gale-Shapley algorithm
# http://en.wikipedia.org/wiki/Stable_marriage_problem

class Man:
    def __init__(self, id, prefs):
        self.id = id
        self.prefs = prefs
        # The index on self.prefs to propose next
        self.next_proposal_index = 0

class Woman:
    def __init__(self, id, prefs):
        self.id = id
        self.prefs = prefs
        self.spouse = None
        self.spouse_rank = None

def match(MP, FP):
    num_round = 0

    M = [Man(id, pref) for id, pref in enumerate(MP)]
    W = [Woman(id, pref) for id, pref in enumerate(FP)]

    free_man = M[:]

    while free_man:
        num_round += 1
        m = free_man.pop()
        w_id = m.prefs[m.next_proposal_index]
        w = W[w_id]
        m.next_proposal_index += 1
        if w.spouse == None:
            w.spouse = m
            w.spouse_rank = w.prefs.index(m.id)
        else:
            try:
                m_rank = w.prefs.index(m.id, 0, w.spouse_rank)
            except ValueError:
                # sorry, w is happily married
                if m.next_proposal_index < len(m.prefs):
                    # in our case, there should always be someone left
                    free_man.append(m)
            else:
                # m wins w and replaces current spouse
                free_man.append(w.spouse)
                w.spouse = m
                w.spouse_rank = m_rank

    couples = [(w.spouse.id, w.id) for w in W]
    couples.sort()
    return couples, num_round


def main(filename):
    data = load(filename)
    log('Loaded %s records from %s' % (len(data), filename))

    Mpref, Fpref = build_pref_matrix(data)
    couples, num_round = match(Mpref, Fpref)
    # print output for facebook
    print '\n'.join(
        '%s %s' % (m_id, w_id+len(Mpref))
            for m_id, w_id in couples)
    log('num_round %s' % num_round)


if __name__ =='__main__':
    filename = sys.argv[1]
    main(filename)