Since the editorial for this problem isn’t out yet. The problem at its heart is quickly detecting even length cycles in a graph, and then colouring the edges in an alternate fashion. How does one go about detecting even length cycles efficiently? This problem seems to be very close to detecting an Euler circuit in a graph. Any help is appreciated.