Construct a monochromatic graph flipping nodes of the edges
This is not a review, but a comment too long to be a comment.

Brute force is almost always wrong. In the tasks like this it is always wrong.

Let the graph has a nodes colored A, and b nodes colored B.

First notice that flipping an edge doesn't change the parity of neither a nor b. From this, it follows immediately that the if both a and b are odd, the graph cannot be made monochromatic.

It is a bit harder to prove the opposite, that is if at least one of a and b is even, a connected graph can be made monochromatic. Prove that given two vertices of a given color there is a sequence of A-B flips so that two vertices of a given color become adjacent. Then use induction.

Summing up, the solution is to identify the connected components of the graph, and for each of them count the color's parities.