Limits 4s, 512 MB

You are given a connected, undirected, unweighted graph. You need to assign one of the two colors Red or Blue to every edge of the graph in such a way that, for each node ∣degreeR−degreeB∣≤1|degree_R-degree_B| \leq 1∣degreeR−degreeB∣≤1. degreeRdegree_RdegreeR of a node is the number of adjacent edges to that node which are colored Red. degreeBdegree_BdegreeB of a node is the number of adjacent edges to that node which are colored Blue.

This is a companion discussion topic for the original entry at https://toph.co/p/red-blue-graph