import itertools


def verify_stable(suitors, suiteds, marriage):
    """ Check that the assignment of suitors to suited is a stable marriage.

    Arguments:
        suitors: a list of Suitors
        suiteds: a list of Suiteds
        marriage: a matching {Suitor: Suited}

    Returns:
        True if the marriage is stable, otherwise a tuple (False, (x, y))
        where x is a Suitor, y is a Suited, and (x, y) are a counterexample
        to the claim that the marriage is stable.
    """

    suited_to_suitor = dict((v, k) for (k, v) in marriage.items())

    def precedes(L, item1, item2): return L.index(item1) < L.index(item2)

    def suitor_prefers(suitor, suited):
        return precedes(suitor.preference_list, suited.id, marriage[suitor].id)

    def suited_prefers(suited, suitor):
        return precedes(suited.preference_list, suitor.id, suited_to_suitor[suited].id)

    for (suitor, suited) in itertools.product(suitors, suiteds):
        if (suited != marriage[suitor]
                and suitor_prefers(suitor, suited)
                and suited_prefers(suited, suitor)):
            return False, (suitor, suited)

    return True