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 MoVPluRunOff(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" and elecType != "csv":
        print("ERROR: unsupported profile type")
        exit()

    # Initialization
    prefcounts = profile.getPreferenceCounts()
    len_prefcounts = len(prefcounts)
    rankmaps = profile.getRankMaps()
    # print(rankmaps)
    ranking = MechanismPlurality().getRanking(profile)
    # print("ranking=", ranking)

    # 1st round: find the top 2 candidates in plurality scores
    # Compute the 1st-place candidate in plurality scores
    max_cand = ranking[0][0][0]

    # Compute the 2nd-place candidate in plurality scores
    # Automatically using tie-breaking rule--numerically increasing order
    if len(ranking[0][0]) > 1:
        second_max_cand = ranking[0][0][1]
        if len(ranking[0][0]) > 2:
            third_max_cand = ranking[0][0][2]
        else:
            third_max_cand = ranking[0][1][0]
    else:
        second_max_cand = ranking[0][1][0]
        if len(ranking[0][1]) > 1:
            third_max_cand = ranking[0][1][1]
        else:
            third_max_cand = ranking[0][2][0]

    top_2 = [max_cand, second_max_cand]
    # 2nd round: find the candidate with maximum plurality score
    dict_top2 = {max_cand: 0, second_max_cand: 0}
    for i in range(len_prefcounts):
        vote_top2 = {key: value for key, value in rankmaps[i].items() if key in top_2}
        # print(vote_top2)
        top_position = min(vote_top2.values())
        keys = [x for x in vote_top2.keys() if vote_top2[x] == top_position]
        for key in keys:
            dict_top2[key] += prefcounts[i]

    # the original winner-- d
    # print("dict_top2=", dict_top2)
    d = max(dict_top2.items(), key=lambda x: x[1])[0]
    c_1 = top_2[0] if top_2[1] == d else top_2[1]
    # the candidate with third highest plurality score
    c_2 = third_max_cand
    # print("d=", d, c_1, c_2)

    Type1_1 = Type1_2 = 0
    plu_d = plu_c_1 = plu_c_2 = 0

    # ------------count the votes of CASE I & II---------------
    for i in range(len_prefcounts):
        if rankmaps[i][d] < rankmaps[i][c_1]:
            Type1_1 += prefcounts[i]
        elif rankmaps[i][d] > rankmaps[i][c_1]:
            Type1_2 += prefcounts[i]

        if rankmaps[i][d] == 1:
            plu_d += prefcounts[i]
        elif rankmaps[i][c_1] == 1:
            plu_c_1 += prefcounts[i]
        elif rankmaps[i][c_2] == 1:
            plu_c_2 += prefcounts[i]
    # print("plu=", plu_d, plu_c_1, plu_c_2)
    # -------------------CASE I------------------------------
    MoV_I = math.floor((Type1_1 - Type1_2)/2) + 1

    # -------------------CASE II-------------------------------
    if math.floor((plu_d + plu_c_2)/2) + 1 <= plu_c_1:
        MoV_II = math.floor((plu_d - plu_c_2)/2) + 1
    else:
        MoV_II = plu_d - math.floor((plu_d + plu_c_1 + plu_c_2)/3) + 1
        # MoV_II = math.floor((plu_d * 2 - plu_c_1 - plu_c_2) / 3) + 1  # old version

    # -------------------CASE III-----------------------------
    MoV_d = dict()
    remaining = sorted(rankmaps[0].keys())
    remaining.remove(d)
    remaining.remove(c_1)

    for e in remaining:
        # ------------count the votes of CASE III---------------
        T1 = T2 = T3 = T4 = T5 = T6 = T7 = T8 = 0
        for i in range(len_prefcounts):
            if rankmaps[i][d] == 1:
                if rankmaps[i][c_1] < rankmaps[i][e]:
                    T1 += prefcounts[i]
                elif rankmaps[i][e] < rankmaps[i][c_1]:
                    T2 += prefcounts[i]
            elif rankmaps[i][c_1] == 1:
                if rankmaps[i][d] < rankmaps[i][e]:
                    T3 += prefcounts[i]
                elif rankmaps[i][e] < rankmaps[i][d]:
                    T4 += prefcounts[i]
            elif rankmaps[i][e] == 1:
                if rankmaps[i][d] < rankmaps[i][c_1]:
                    T5 += prefcounts[i]
                elif rankmaps[i][c_1] < rankmaps[i][d]:
                    T6 += prefcounts[i]
            else:
                if rankmaps[i][d] < rankmaps[i][e]:
                    T7 += prefcounts[i]
                elif rankmaps[i][e] < rankmaps[i][d]:
                    T8 += prefcounts[i]

        if math.floor((T3 + T4 + T5 + T6)/2) + 1 <= T1 + T2:
            CHANGE1 = math.floor((T3 + T4 - T5 - T6)/2) + 1
        else:
            CHANGE1 = T3 + T4 - T1 -T2 + 1

        x = min(T3, CHANGE1)
        if T1 + T2 + T3 + T7 - x < T4 + T5 + T6 + T8 + x:
            MoV_d[e] = CHANGE1
        else:
            CHANGE2 = math.floor((T1 + T2 + T3 + T7 - T4 - T5 - T6 - T8)/2) - x + 1
            MoV_d[e] = CHANGE1 + CHANGE2

    MoV_III = min(MoV_d.items(), key=lambda x: x[1])[1]
    # ------------------------Overall MoV---------------------------------
    # print(MoV_d)
    # print(MoV_I, MoV_II, MoV_III)
    MoV = min(MoV_I, MoV_II, MoV_III)

    return MoV