Let us observe the following simple algorithm:

1. Place the MPs to parties in any way.
2. As long as there is an MP ~K~ for which the required condition is not met, switch ~K~ to the opposing party.

It is not clear right away whether this algorithm is going to finish or we will keep switching the MPs eternally. But the following is clear: if the algorithm finishes, it finds the required solution.

Luckily, not only does the upper algorithm finish, but it is fast enough. Let's prove it!

Remember that each MP is arguing with at most five other MPs. Let's examine the number of intraparty arguments. We switch the MP if he does not meet the required condition. In other words, if he causes at least three intraparty arguments. By switching him, we remove these arguments, possibly creating new intraparty arguments in the other party, but at most two (with his remaining enemies). It follows: with each switch, the total number of intraparty arguments decreases. Since the initial number of intraparty arguments is at most ~5N/2~, the algorithm must finish after at most ~5N/2~ switches.