AtCoder Grand Contest 033 - Complexity

Note the unusual memory limit.

For a rectangular grid where each square is painted white or black, we define its complexity as follows:

* If all the squares are black or all the squares are white, the complexity is 0.
* Otherwise, divide the grid into two subgrids by a line parallel to one of the sides of the grid, and let c_1 and c_2 be the complexities of the subgrids. There can be multiple ways to perform the division, and let m be the minimum value of \max(c_1, c_2) in those divisions. The complexity of the grid is m+1.



You are given a grid with H horizontal rows and W vertical columns where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is `#` if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is `.` if that square is white.

Find the complexity of the given grid.

Constraints

* 1 \leq H,W \leq 185
* A_{ij} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}


Output

Print the complexity of the given grid.

Examples

Input

3 3
...
.##
.##


Output

2


Input

6 7
.####.#
....#.
....#.
....#.
.####.#
....##


Output

4

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(H, W) = map(int, input().split())
A = [[1 if a == '#' else 0 for a in input()] for _ in range(H)]
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]
for i in range(H):
	Xi = X[i]
	Yi = Y[i]
	for j in range(W):
		Xi[j][i] = j
		Yi[j][j] = i
for i in range(H):
	Xi = X[i]
	Ai = A[i]
	for j in range(W - 1)[::-1]:
		if Ai[j] == Ai[j + 1]:
			Xi[j][i] = Xi[j + 1][i]
for i in range(H - 1)[::-1]:
	Yi = Y[i]
	Yi1 = Y[i + 1]
	Ai = A[i]
	Ai1 = A[i + 1]
	for j in range(W):
		if Ai[j] == Ai1[j]:
			Yi[j][j] = Yi1[j][j]
for i in range(H):
	Xi = X[i]
	Ai = A[i]
	for j in range(W):
		Xij = Xi[j]
		for ii in range(i + 1, H):
			if A[ii][j] != Ai[j]:
				break
			Xij[ii] = min(Xij[ii - 1], X[ii][j][ii])
for i in range(H):
	Yi = Y[i]
	Ai = A[i]
	for j in range(W):
		Yij = Yi[j]
		for jj in range(j + 1, W):
			if Ai[jj] != Ai[j]:
				break
			Yij[jj] = min(Yij[jj - 1], Yi[jj][jj])
for k in range(16):
	if X[0][0][H - 1] == W - 1:
		print(k)
		break
	elif k == 15:
		print(16)
		break
	for i in range(H):
		Xi = X[i]
		Yi = Y[i]
		for j in range(W):
			Xij = Xi[j]
			Yij = Yi[j]
			for ii in range(i, H):
				Xijii = Xij[ii]
				if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
					Xij[ii] = X[i][Xijii + 1][ii]
			for jj in range(j, W):
				Yijjj = Yij[jj]
				if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
					Yij[jj] = Y[Yijjj + 1][j][jj]
			jj = W - 1
			for ii in range(i, H):
				while jj >= j and Yij[jj] < ii:
					jj -= 1
				if jj >= j:
					Xij[ii] = max(Xij[ii], jj)
			ii = H - 1
			for jj in range(j, W):
				while ii >= i and Xij[ii] < jj:
					ii -= 1
				if ii >= i:
					Yij[jj] = max(Yij[jj], ii)


(h, w) = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))
WR2 = list(range(w - 2, -1, -1))
hor = [[[-1] * h for _ in WR] for _ in HR]
ver = [[[-1] * w for _ in WR] for _ in HR]
for i in HR:
	hi = hor[i]
	fi = field[i]
	curr = hi[-1][i] = w - 1
	curc = fi[-1]
	for j in WR2:
		if fi[j] != curc:
			curr = hi[j][i] = j
			curc = fi[j]
		else:
			hi[j][i] = curr
for i in HR:
	hi = hor[i]
	vi = ver[i]
	fi = field[i]
	for j in WR:
		hij = hi[j]
		vij = vi[j]
		fij = fi[j]
		curr = hij[i]
		for k in HR[i + 1:]:
			if field[k][j] != fij:
				break
			curr = hij[k] = min(curr, hor[k][j][k])
		curr = j
		for k in range(h - 1, i - 1, -1):
			h_ijk = hij[k]
			if h_ijk == -1:
				continue
			while curr <= h_ijk:
				vij[curr] = k
				curr += 1
ans = 0
while True:
	if hor[0][0][-1] == w - 1:
		break
	for i in HR:
		hi = hor[i]
		vi = ver[i]
		for j in WR:
			hij = hi[j]
			vij = vi[j]
			for k in HR[i:]:
				h_ijk = hij[k]
				if h_ijk == -1:
					break
				if h_ijk == w - 1:
					continue
				hij[k] = max(h_ijk, hi[h_ijk + 1][k])
			for k in WR[j:]:
				v_ijk = vij[k]
				if v_ijk == -1:
					break
				if v_ijk == h - 1:
					continue
				vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])
			curr = j
			for k in range(h - 1, i - 1, -1):
				h_ijk = hij[k]
				if h_ijk == -1:
					continue
				while curr <= h_ijk:
					vij[curr] = max(vij[curr], k)
					curr += 1
			curb = i
			for k in range(w - 1, j - 1, -1):
				v_ijk = vij[k]
				if v_ijk == -1:
					continue
				while curb <= v_ijk:
					hij[curb] = max(hij[curb], k)
					curb += 1
	ans += 1
print(ans)