Consider the sum of degrees of the vertices painted red. Here, the edges connecting vertices painted red are counted twice each, and those connecting vertices painted in different colors are counted once each.

Let \(S\) be the sum of degrees of the red vertices, \(R\) be the number of edges connecting vertices painted red, and \(D\) be the number of edges connecting vertices painted in different colors; then we have

\[S = 2R + D.\]

Considering the remainder when divided by \(2\) we have

\[S \equiv D \pmod{2}.\]

Thus, \(D\) is even if and only if \(S\) is even, i.e. there are even number of red vertices whose degrees are odd.

By iterating the possible numbers of red vertices whose degrees are odd, the problem can be solved in a total of \(O(N + M)\) time.

Sample code (C++)