Could anybody give me any hints about solution.
There was posted one algorithm but it is wrong -
there is a counter-example for it. So, anybody who
has AC, tell me please how to solve it.

Sorry, i've misunderstood some things in solution.