My algo works O(N^3) at 0.015 sec.
Solution always exist.

Idea:
We must paint first half of edge in 'Y' and second half in 'G'.

1)Delete cycles (if the edge belongs to the cycle then we delete it from the graph) and paint edges;
2)Paint a tree.


Edited by author 27.08.2015 15:36