Given a graph with at most 2*10^5 nodes and 2*10^5 edges, bicolor the graph such that the difference between the number of nodes with each color is minimized, and print out that difference.

I am able to bicolor each of the connected components, and find the number of each color in each component. I tried to make the final step of finding the minimum difference into the subset sum problem before realizing that there are restrictions on what numbers can go together.

E.g. I have components (Red, Blue) as (1, 5) and (2, 4); the optimal subset sum solution would normally be to put the 1 and 5 together, and the 2 and 4 together. However, the (1, 5) pair and (2, 4) pair are component pairs, which is not allowed.

Please help, and thanks in advance!