Even after anti-greedy tests were added, it is possibly to solve the problem with greedy algo. Just randomize directions in which you make "greedy walk" of the incidence matrix. The best thing is that it is impossible to kill such an algo with any anti-greesy tests! =)

I have proven greedy solution (with O(N^3) output size)