Компоненти зв'язності в сітці Насера#13101

Компоненти зв'язності в сітці Насера

2 секунди

256 мегабайтів

Насер дає вам сітку з $n$ рядків та $m$ стовпців, яка містить цілі числа.

Вам потрібно вибрати стовпець $c$ $(1 \leq c < m)$ (1 \le c < m), щоб розділити сітку на дві частини:

Ліва частина: стовпці з $1$ до $c$ (включно).
Права частина: стовпці з $c + 1$ c+1 до $m$ (включно).

Дві клітинки вважаються сусідніми, якщо вони мають спільну сторону (зверху, знизу, зліва або справа). Дві сусідні клітинки, що лежать в одній частині, вважаються з'єднаними, якщо вони містять рівні значення. Компонента зв'язності — це максимальна за включенням група клітинок, у якій від будь-якої клітинки можна дістатися до будь-якої іншої через ланцюжок з'єднаних сусідніх клітинок.

Наприклад, у сітці:

113123222

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

Якщо ми розділимо її за стовпцем $c = 1$ c=1, то ліва частина буде такою:

113

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

Найбільша компонента зв'язності в лівій частині має розмір $2$ (дві клітинки зі значенням $1$ ). Права частина:

123222

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

Найбільша компонента зв'язності у правій частині має розмір $4$ (чотири клітинки зі значенням $2$ ).

Нехай $L$ — розмір найбільшої компоненти зв'язності в лівій частині, а $R$ — розмір найбільшої компоненти зв'язності у правій частині.

Ваше завдання — вибрати стовпець $c$ так, щоб мінімізувати $∣ L - R ∣$ |L - R|.

У наведеному вище прикладі, якщо вибрати $c = 1$ c=1, то $L = 2$ L=2, $R = 4$ R=4 і $∣ L - R ∣ = 2$ |L-R|=2. Якщо вибрати $c = 2$ c=2, то $L$ та $R$ обчислюються для нового розбиття, і ми беремо мінімум за всіма варіантами вибору $c$ .

Вхідні дані

Кожен тест містить декілька тестових випадків. Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — кількість тестових випадків. Далі йде опис тестових випадків.

Перший рядок кожного тестового випадку містить два цілих числа $n$ та $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) — кількість рядків та стовпців.

Кожен з наступних $n$ рядків містить $m$ цілих чисел $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) — елементи сітки.

Гарантується, що сума $n \cdot m$ n \cdot m за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — мінімальне можливе значення $∣ L - R ∣$ |L - R|.

Приклади

Приклад 1

Оцінювання

Підзадача $1$ ( $50$ балів) : $(n = 1)$ (n = 1)
Підзадача $2$ ( $50$ балів) : $(m \leq 50)$ (m \le 50)
Підзадача $3$ ( $200$ балів) : Без додаткових обмежень.