In a parliament
For each person, compute his animosity level by subtracting the number of enemies from the opposite group from the number of enemies in his own group. Now put the people into 2 groups so that the total animosity level of all of them is as little as possible. If there is a person, who has more enemies in his own group than the opposite one, then by transferring him to the other group, we will reduce the total animosity level of the people. However, this yields a contradiction.