Returns an integer that is equal to the margin of victory of the election profile, that is,
    the smallest number k such that changing k votes can change the winners.

    :ivar Profile profile: A Profile object that represents an election profile.

def AppMoVMaximin(profile):
    """
    Returns an integer that is equal to the margin of victory of the election profile, that is,
    the smallest number k such that changing k votes can change the winners.

    :ivar Profile profile: A Profile object that represents an election profile.
    """

    # Currently, we expect the profile to contain complete ordering over candidates.
    elecType = profile.getElecType()
    if elecType != "soc" and elecType != "toc":
        print("ERROR: unsupported profile type")
        exit()

    # Initialization
    n = profile.numVoters
    m = profile.numCands

    # Compute the original winner d
    wmgMap = profile.getWmg()
    # Initialize each Copeland score as infinity.
    maximinscores = {}
    for cand in wmgMap.keys():
        maximinscores[cand] = float("inf")

    # For each pair of candidates, calculate the number of votes in which one beat the other.

    # For each pair of candidates, calculate the number of times each beats the other.
    for cand1, cand2 in itertools.combinations(wmgMap.keys(), 2):
        if cand2 in wmgMap[cand1].keys():
            maximinscores[cand1] = min(maximinscores[cand1], wmgMap[cand1][cand2])
            maximinscores[cand2] = min(maximinscores[cand2], wmgMap[cand2][cand1])
    d = max(maximinscores.items(), key=lambda x: x[1])[0]

    #Compute c* = argmax_c maximinscores(c)
    scores_without_d = maximinscores.copy()
    del scores_without_d[d]

    c_star = max(scores_without_d.items(), key=lambda x: x[1])[0]

    return (maximinscores[d] - maximinscores[c_star])/2