Since my solution got AC, there IS a limit on k... or the tests are too weak.

If the pairs are all different, there will be at most M*N different pairs.(but it doesn't say it...)