Componentes en la cuadrícula de Nasser#13101

Componentes en la cuadrícula de Nasser

2 segundos

256 megabytes

Nasser te da una cuadrícula de $n$ filas y $m$ columnas que contiene números enteros.

Debes elegir una columna $c$ $(1 \leq c < m)$ (1 \le c < m) para dividir la cuadrícula en dos partes:

Parte izquierda: las columnas de $1$ a $c$ (inclusive).
Parte derecha: las columnas de $c + 1$ c+1 a $m$ (inclusive).

Dos celdas se consideran adyacentes si comparten un lado (arriba, abajo, izquierda o derecha). Dos celdas adyacentes que pertenecen a la misma parte están conectadas si contienen valores iguales. Una componente conexa es un grupo maximal de celdas en el que cada par de celdas se puede alcanzar mutuamente a través de una cadena de celdas adyacentes conectadas.

Por ejemplo, en la cuadrícula:

113123222

\begin{pmatrix} 1 & 1 & 2 \\ 1 & 2 & 2 \\ 3 & 3 & 2 \end{pmatrix}

Si dividimos por la columna $c = 1$ c=1, la parte izquierda es:

113

\begin{pmatrix} 1 \\ 1 \\ 3 \end{pmatrix}

La mayor componente conexa de la parte izquierda tiene tamaño $2$ (los dos $1$ ). La parte derecha es:

123222

\begin{pmatrix} 1 & 2 \\ 2 & 2 \\ 3 & 2 \end{pmatrix}

La mayor componente conexa de la parte derecha tiene tamaño $4$ (los cuatro $2$ ).

Sea $L$ el tamaño de la mayor componente conexa de la parte izquierda y sea $R$ el tamaño de la mayor componente conexa de la parte derecha.

Tu tarea es elegir una columna $c$ que minimice $∣ L - R ∣$ |L - R|.

En el ejemplo anterior, si elegimos $c = 1$ c=1, entonces $L = 2$ L=2, $R = 4$ R=4 y $∣ L - R ∣ = 2$ |L-R|=2. Si elegimos $c = 2$ c=2, entonces $L$ y $R$ se calculan para la nueva división, y tomamos el mínimo sobre todas las elecciones de $c$ .

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene un único entero $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ( $1 \leq n$ 1 \le n, $2 \leq m$ 2 \le m, $n \cdot m \leq 2 \cdot 1 0^{5}$ n \cdot m \le 2 \cdot 10^5) — el número de filas y de columnas.

Cada una de las siguientes $n$ líneas contiene $m$ enteros $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ a_{i,1}, a_{i,2}, \ldots, a_{i,m} ( $1 \leq a_{i, j} \leq 1 0^{9}$ 1 \le a_{i,j} \le 10^9) — los elementos de la cuadrícula.

Se garantiza que la suma de $n \cdot m$ n \cdot m sobre todos los casos de prueba no excede $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Salida

Para cada caso de prueba, imprime un único entero — el mínimo valor posible de $∣ L - R ∣$ |L - R|.

Ejemplos

Ejemplo 1

Puntuación

Subtarea $1$ ( $50$ puntos) : $(n = 1)$ (n = 1)
Subtarea $2$ ( $50$ puntos) : $(m \leq 50)$ (m \le 50)
Subtarea $3$ ( $200$ puntos) : Sin restricciones adicionales.