Nasser'in Izgarasındaki Bileşenler#13101

Nasser'in Izgarasındaki Bileşenler

2 saniye

256 megabayt

Nasser size tam sayılardan oluşan $n$ satır ve $m$ sütunluk bir ızgara veriyor.

Izgarayı iki parçaya bölmek için bir $c$ $(1 \leq c < m)$ (1 \le c < m) sütunu seçmelisiniz:

Sol parça: $1$ 'den $c$ 'ye kadar olan (dahil) sütunlar.
Sağ parça: $c + 1$ c+1'den $m$ 'ye kadar olan (dahil) sütunlar.

İki hücre bir kenarı paylaşıyorsa (yukarı, aşağı, sol veya sağ) komşu kabul edilir. Aynı parçada bulunan iki komşu hücre eşit değerler içeriyorsa bağlı sayılır. Bağlı bileşen, içindeki her hücre çiftinin birbirine bağlı komşu hücreler zinciri üzerinden ulaşabildiği maksimal hücre grubudur.

Örneğin, şu ızgarada:

113123222

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

Eğer $c = 1$ c=1 sütunundan bölersek, sol parça şöyle olur:

113

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

Sol parçadaki en büyük bağlı bileşenin boyutu $2$ 'dir (iki tane $1$ ). Sağ parça ise şöyledir:

123222

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

Sağ parçadaki en büyük bağlı bileşenin boyutu $4$ 'tür (dört tane $2$ ).

$L$ , sol parçadaki en büyük bağlı bileşenin boyutu; $R$ ise sağ parçadaki en büyük bağlı bileşenin boyutu olsun.

Göreviniz, $∣ L - R ∣$ |L - R| değerini en küçük yapacak bir $c$ sütunu seçmektir.

Yukarıdaki örnekte, $c = 1$ c=1 seçersek $L = 2$ L=2, $R = 4$ R=4 ve $∣ L - R ∣ = 2$ |L-R|=2 olur. $c = 2$ c=2 seçersek, $L$ ve $R$ yeni bölünmeye göre hesaplanır ve tüm $c$ seçimleri üzerinden minimumu alırız.

Giriş

Her test birden fazla test durumu içerir. İlk satırda test durumlarının sayısını belirten tek bir tam sayı $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) verilir. Ardından test durumlarının açıklaması gelir.

Her test durumunun ilk satırında satır ve sütun sayısını belirten iki tam sayı $n$ ve $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) verilir.

Sonraki $n$ satırın her birinde ızgaranın elemanları olan $m$ tam sayı $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) verilir.

Tüm test durumları üzerinden $n \cdot m$ n \cdot m toplamının $2 \cdot 1 0^{5}$ 2 \cdot 10^5'i aşmadığı garanti edilir.

Çıktı

Her test durumu için tek bir tam sayı — $∣ L - R ∣$ |L - R| ifadesinin mümkün olan en küçük değerini yazdırın.

Örnekler

Örnek 1

Puanlama

Altgörev $1$ ( $50$ puan) : $(n = 1)$ (n = 1)
Altgörev $2$ ( $50$ puan) : $(m \leq 50)$ (m \le 50)
Altgörev $3$ ( $200$ puan) : Ek kısıt yoktur.