Red Blue Graph

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