You can run dfs at each component, then select the type of color with larger amount of node covered and add it to the answer. (If there exists a component which is not bipartite, return error.)

Edit: Oh.. I misinterpreted the constraints, hold on. Gotta rethink it a bit more.

Edit2: I am raising my white flag, I don't know and would like to know a decent solution for this problem. The corner cases just kills the greedy approach and the graph nature and the situation makes dp and point compression much more complicated.