Hello everyone,

I recently gave this gym contest (virtual) and couldn't come up with a solution to problem G.

The problem is as follows: Given a graph with *n* ( ≤ 10^{3}) nodes and some edges ( ≤ *n* *(*n* - 1) / 2). Let's denote **m as the maximum degree** in the graph. Now you need to color the graph with 2 colors with the constraint that **each node can have atmost m / 2 neighbors with the same color as the node itself** . Given the above info, give the coloring of the graph.

Please help me solve it.

Thanks.