#include "bits/stdc++.h"
#define YES "YES"
#define Yes "Yes"
#define NO "NO"
#define No "No"
#define YESNO OUT(three(solve(),YES,NO))
#define YesNo OUT(three(solve(),Yes,No))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b-1,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int short
#define zero 0LL
#define pb PB
using namespace std;
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef short LL;
typedef long double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr, Vpr, greater<pr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
int dx[] = { 0,1,0,-1,1,1,-1,-1,0 }, dy[] = { 1,0,-1,0,1,-1,1,-1,0 };
const int SIZE1 = 10; // ;; 5e5 + 1000;
const int SIZE2 = 1010;
const int SIZE3 = 188;
const int SIZE = SIZE3;
const LL p = 9973;
const LL INF = 1000;
const long double EPS = 1e-7;
ut N, M, K, L, H, W, Q, D, T;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
Vpr edges[SIZE];
signed maps[SIZE2][SIZE2];
short DP[2][SIZE][SIZE][SIZE][18];

signed sum[SIZE2][SIZE2];
bool isOne(signed sy, signed sx, signed ey, signed  ex) {
	sy++;
	sx++;
	ey++;
	ex++;
	signed sums = sum[ey][ex] - sum[ey][sx - 1] - sum[sy - 1][ex] + sum[sy - 1][sx - 1];
	return sums == 0 or sums == (ey - sy + 1)*(ex - sx + 1);
}

short solve2(bool dir, LL sy, LL sx, LL e, LL comp) {
	if (sy < 0 or sx < 0 or e < 0) return -INF;
	if (DP[dir][sy][sx][e][comp] != -INF * 2) return DP[dir][sy][sx][e][comp];
	DP[dir][sy][sx][e][comp] = 0;
	if (comp == 0) {
		if (dir) {

			int ss = sy, ee = H - 1;
			while (ss <= ee) {
				LL f = (ss + ee) / 2;
				if (isOne(sy, sx, f, e)) {
					ss = f + 1;
				}
				else {
					ee = f - 1;
				}
			}
			//			if (ee < sy) ee = -INF;
						//cout << dir << " " << sy << " " << e << " " << comp << " " << ee << endl;
			return DP[dir][sy][sx][e][comp] = ee;
		}
		else {
			int ss = sx, ee = W - 1;
			while (ss <= ee) {
				LL f = (ss + ee) / 2;
				if (isOne(sy, sx, e, f)) {
					ss = f + 1;
				}
				else {
					ee = f - 1;
				}
			}
			//		if (ee < sx) ee = -INF;
			return DP[dir][sy][sx][e][comp] = ee;
		}
	}
	LL ans = -INF;
	if (dir) {
		MX(ans, solve2(dir, solve2(dir, sy, sx, e, comp - 1) + 1, sx, e, comp - 1));
		int ss = sy, ee = H - 1;
		while (ss <= ee) {
			LL f = (ss + ee) / 2;
			if (solve2(!dir, sy, solve2(!dir, sy, sx, f, comp - 1) + 1, f, comp - 1) >= e) {
				ss = f + 1;
			}
			else {
				ee = f - 1;
			}
		}
		//	if (ee < sy) ee = -INF;
		MX(ans, ee);
	}
	else {
		MX(ans, solve2(dir, sy, solve2(dir, sy, sx, e, comp - 1) + 1, e, comp - 1));
		int ss = sx, ee = W - 1;
		while (ss <= ee) {
			LL f = (ss + ee) / 2;
			if (solve2(!dir, solve2(!dir, sy, sx, f, comp - 1) + 1, sx, f, comp - 1) >= e) {
				ss = f + 1;
			}
			else {
				ee = f - 1;
			}
		}
		//	if (ee < sx) ee = -INF;
		MX(ans, ee);
	}
	//cout << ans << endl;
	return DP[dir][sy][sx][e][comp] = ans;
}
LL solve() {
	cin >> H >> W;
	REP(i, H) {
		string s;
		cin >> s;
		REP(j, s.size()) {
			maps[i][j] = s[j] == '#';
		}
	}
	REP(c, 2) REP(i, SIZE) REP(j, SIZE) REP(k, SIZE) REP(l, 18) DP[c][i][j][k][l] = -INF * 2;
	EFOR(i, 1, H) EFOR(j, 1, W) {
		sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + maps[i - 1][j - 1];
	}
	REP(i, 30) {
		if (solve2(0, 0, 0, H - 1, i) == W - 1 or solve2(1, 0, 0, W - 1, i) == H - 1) {
			cout << i << endl;
			break;
		}
		else {
			//	cout << solve2(0, 0, 0, H - 1, i) << endl;
		}
	}
	return 0;
}
signed main() {

	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	solve();
	//	cin >> N;
	return 0;
}


Measured memory_bytes: 472064