This problem is very simple.
I think it can be more interesting if one of dimensions can be odd.

For example:
4 5
1 1 2 2 3
4 5 5 6 3
4 7 7 6 10
8 8 9 9 10

Another example:
2 3
1 2 3
1 2 3

Anyway, bipartie algo does not depend on that :)

That tests aren't correct.
"M and N are EVEN numbers not exceeding 100"