%:pragma GCC optimize("Ofast", "inline")
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
#define type short
const int N = 190;
int sum[N][N], n, m;
char s[N][N];
int ok[N][N][N];
type dp[N][N][N][17]; bool vis[N][N][N][17];

inline int getsum(int l, int r, int u, int d) {
	return sum[d][r] - sum[u - 1][r] - sum[d][l - 1] + sum[u - 1][l - 1];
}

inline bool valid(int l, int r, int u, int d) {
	int a = (d - u + 1) * (r - l + 1);
	int s = sum[d][r] - sum[u - 1][r] - sum[d][l - 1] + sum[u - 1][l - 1];
	return s == 0 || s == a;
}

inline int check(int l, int r, int x) {
	if (ok[l][r][x] != -1) return ok[l][r][x];
	int &cur = ok[l][r][x];
	if (valid(l, r, x, x)) return cur = 1;
	else {
		if (s[x][l] == s[x][l + 1]) return cur = check(l + 1, r, x);
		else return cur = valid(l + 1, r, x, x);
	}	
}	

inline type DP(int l, int r, int x, int k) {
	if (x > n) return n;
	if (vis[l][r][x][k]) return dp[l][r][x][k];
	vis[l][r][x][k] = true;
	type &ans = dp[l][r][x][k] = 0;
	if (k == 0) {
		if (!valid(l, r, x, x)) return ans;
		int low = x, high = n;
		while (low < high) {
			int mid = low + (high - low + 1) / 2;
			if (valid(l, r, x, mid)) low = mid;
			else high = mid - 1;
		}
		// cout << l << " " << r << " " << x << " " << k << " " << low << "\n";
		return ans = low;
	}
	// shu

	if (l < r) {
		int low = l, high = r - 1;
		while (low < high) {
			int mid = low + (high - low + 1) / 2;
			if (DP(l, mid, x, k - 1) >= DP(mid + 1, r, x, k - 1)) low = mid;
			else high = mid - 1;
		}
		if (min(DP(l, low, x, k - 1), DP(low + 1, r, x, k - 1)) < x && k == 1) {
			// cout << l << " " << r << " " << x << " " << check(l, r, x) << "\n";
			if (check(l, r, x)) {
				int ll = l, rr = r - 1;
				while (ll < rr) {
					int mm = (ll + rr + 1) / 2;
					if (valid(l, mm, x, x)) ll = mm;
					else rr = mm - 1;
				}
				ans = x;
				low = ll;
				// cout << ll << "\n";
			}
			// cout << ans << "\n";
		}
	// 	cout << DP(l, low + 1, x, k - 1) << " " << DP(low + 2, r, x, k - 1) << "\n";
	// cout << l << " " << r << " " << x << " " << k << " " << low << " TTTtt\n";
	for (int delta = -5; delta <= 5; delta++)
		if (l <= low + delta && low + 1 + delta <= r)
			ans = max(ans, min(DP(l, low + delta, x, k - 1), DP(low + 1 + delta, r, x, k - 1)));
	}
	// heng
	type cut = DP(l, r, x, k - 1);
	if (cut >= x) {
		type nd = DP(l, r, cut + 1, k - 1);
		ans = max(ans, nd);
	}

	// cout << l << " " << r << " " << x << " " << k << " " << ans <<"\n";
	return ans;
}

int main(void) {
	memset(ok, -1, sizeof ok);
	read(n); read(m);
	rep (i, n) scanf("%s", s[i] + 1);
	rep (i, n) rep (j, m) sum[i][j] = s[i][j] = s[i][j] == '#';
	rep (i, n) rep (j, m) sum[i][j] += sum[i][j - 1];
	rep (i, n) rep (j, m) sum[i][j] += sum[i - 1][j];
	// rep (i, n) rep (j, m) cout << sum[i][j] << " \n"[j == m];
	// cout << valid(1, 2, 3, 3) << "\n";
	// cout << DP(1, 3, 1, 2) << "\n";
	// return 0;
	int x = 0;
	while (DP(1, m, 1, x) < n) ++x;
	cout << x << "\n";
}


Measured memory_bytes: 363904