You are given an $$$n \times m$$$ rectangular grid of colored balls, where each ball can be one of three colors. In a single step, you may swap any two balls. Determine the minimum number of steps required to arrange the balls such that the grid is partitioned into single-colored rectangles — one rectangle for each color present.
The first line of the input contains two integers $$$n$$$ and $$$m$$$. The following $$$n$$$ lines each contain $$$m$$$ integers (1, 2, or 3), representing the colors of the balls.
Output a single integer: the minimum number of steps required. If no solution exists, output -1.
Subtask 1 (up to 20 points): $$$1 \le n, m \le 10$$$; the balls can only be of color 1 or 2.
Subtask 2 (up to 20 points): $$$1 \le n, m \le 1000$$$; the balls can only be of color 1 or 2.
Subtask 3 (up to 24 points): $$$1 \le n, m \le 10$$$; the balls can be of color 1, 2, or 3.
Subtask 4 (up to 36 points): $$$1 \le n, m \le 1000$$$; the balls can be of color 1, 2, or 3.
3 41 2 1 12 1 1 33 3 3 1
2
2 21 11 1
0
2 31 1 11 1 2
-1
In the first example, it is sufficient to swap the first two balls in the first row and the last two balls in the last column.
A note for those using Python: You can read a sequence of space-separated integers as follows:
c = [int(x) for x in input().split()]
