Nasserin cədvəlindəki əlaqəli komponentlər#13101

Nasserin cədvəlindəki əlaqəli komponentlər

2 saniyə

256 meqabayt

Nasser sizə tam ədədlərdən ibarət $n$ sətir və $m$ sütunluq cədvəl verir.

Cədvəli iki hissəyə bölmək üçün $c$ $(1 \leq c < m)$ (1 \le c < m) sütununu seçməlisiniz:

Sol hissə: $1$ -dən $c$ -yə qədər (daxil olmaqla) sütunlar.
Sağ hissə: $c + 1$ c+1-dən $m$ -ə qədər (daxil olmaqla) sütunlar.

İki xana ümumi tərəfə malikdirsə (yuxarı, aşağı, sol və ya sağ), onlar qonşu sayılır. Eyni hissədə yerləşən iki qonşu xana bərabər qiymətlər saxlayırsa, onlar birləşmiş sayılır. Əlaqəli komponent — elə maksimal xanalar qrupudur ki, onun istənilən iki xanası birləşmiş qonşu xanalar zənciri vasitəsilə bir-birindən əldə oluna bilir.

Məsələn, aşağıdakı cədvəldə:

113123222

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

Əgər $c = 1$ c=1 sütununda bölsək, sol hissə belə olar:

113

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

Sol hissədəki ən böyük əlaqəli komponentin ölçüsü $2$ -dir (iki ədəd $1$ ). Sağ hissə isə belədir:

123222

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

Sağ hissədəki ən böyük əlaqəli komponentin ölçüsü $4$ -dür (dörd ədəd $2$ ).

Tutaq ki, $L$ — sol hissədəki ən böyük əlaqəli komponentin ölçüsü, $R$ isə sağ hissədəki ən böyük əlaqəli komponentin ölçüsüdür.

Sizin vəzifəniz $∣ L - R ∣$ |L - R| qiymətini minimuma endirən $c$ sütununu seçməkdir.

Yuxarıdakı misalda, əgər $c = 1$ c=1 seçsək, onda $L = 2$ L=2, $R = 4$ R=4 və $∣ L - R ∣ = 2$ |L-R|=2 olar. Əgər $c = 2$ c=2 seçsək, $L$ və $R$ yeni bölgü üçün hesablanır və biz bütün mümkün $c$ seçimləri üzrə minimumu götürürük.

Giriş

Hər test bir neçə test nümunəsindən ibarətdir. Birinci sətirdə bir tam ədəd $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test nümunələrinin sayı verilir. Sonra test nümunələrinin təsviri gəlir.

Hər test nümunəsinin birinci sətrində iki tam ədəd $n$ və $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) — sətirlərin və sütunların sayı verilir.

Sonrakı $n$ sətrin hər birində $m$ tam ədəd $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) — cədvəlin elementləri verilir.

Bütün test nümunələri üzrə $n \cdot m$ n \cdot m cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i keçmədiyi təmin edilir.

Çıxış

Hər test nümunəsi üçün bir tam ədəd — $∣ L - R ∣$ |L - R| ifadəsinin mümkün minimum qiymətini çıxarın.

Nümunələr

Nümunə 1

Bal hesablama

Altməsələ $1$ ( $50$ bal) : $(n = 1)$ (n = 1)
Altməsələ $2$ ( $50$ bal) : $(m \leq 50)$ (m \le 50)
Altməsələ $3$ ( $200$ bal) : Əlavə məhdudiyyət yoxdur.