Nasser's Grid Components#13101
Nasser gives you a grid of rows and columns containing integers.
You need to choose a column (1 \le c < m) to split the grid into two parts:
Left part: columns to (inclusive).
Right part: columns c+1 to (inclusive).
Two cells are considered adjacent if they share an edge (up, down, left, or right). Two adjacent cells in the same part are connected if they contain equal values. A connected component is a maximal group of cells where every pair of cells can be reached from one another through a chain of connected adjacent cells.
For example, in the grid:
If we split at column c=1, the left part is:
The largest connected component in the left part has size (the two s). The right part is:
The largest connected component in the right part has size (the four s).
Let be the size of the largest connected component in the left part, and be the size of the largest connected component in the right part.
Your task is to choose a column to minimize |L - R|.
In the example above, if we choose c=1, then L=2, R=4, and |L-R|=2. If we choose c=2, then and are computed for the new split, and we take the minimum over all choices of .
Each test contains multiple test cases. The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers and (1 \le n, 2 \le m, n \cdot m \le 2 \cdot 10^5) — the number of rows and columns.
Each of the next lines contains integers a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^9) — the elements of the grid.
It is guaranteed that the sum of n \cdot m over all test cases does not exceed 2 \cdot 10^5.
For each test case, output a single integer — the minimum possible value of |L - R|.
Example 1
Subtask ( points) : (n = 1)
Subtask ( points) : (m \le 50)
Subtask ( points) : No additional constraints.