/**
 *    author:  otera    
**/
#include<iostream>
#include<string> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm> 
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int h, w;
vector<vector<char>> a;
vector<vector<int>> sum;

int dp1[200][200][200][2];
int dp2[200][200][200][2];

void solve() {
	cin >> h >> w;
    a.assign(h, vector<char>(w));
    sum.assign(h + 1, vector<int>(w + 1, 0));
    rep(i, h) {
        rep(j, w) {
            cin >> a[i][j];
            sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (a[i][j] == '#');
        }
    }
    // 初期化
    rep(i, 200) {
        rep(j, 200) {
            rep(k, 200) {
                rep(l, 2) {
                    dp1[i][j][k][l] = dp2[i][j][k][l] = -1;
                }
            }
        }
    }
    for(int h1 = 0; h1 <= h; ++ h1) {
        for(int h2 = 0; h2 <= h; ++ h2) {
            int w2 = 0;
            for(int w1 = 0; w1 <= w; ++ w1) {
                if(w2 < w1) w2 = w1;
                while(w2 < w && ((sum[h2][w2 + 1] - sum[h1][w2 + 1] - sum[h2][w1] + sum[h1][w1] == 0) || (sum[h2][w2 + 1] - sum[h1][w2 + 1] - sum[h2][w1] + sum[h1][w1] == (w2 + 1 - w1) * (h2 - h1)))) ++ w2;
                dp1[h1][h2][w1][0] = w2;
            }
        }
    }
    for(int w1 = 0; w1 <= w; ++ w1) {
        for(int w2 = 0; w2 <= w; ++ w2) {
            int h2 = 0;
            for(int h1 = 0; h1 <= h; ++ h1) {
                if(h2 < h1) h2 = h1;
                while(h2 < h && ((sum[h2 + 1][w2] - sum[h1][w2] - sum[h2 + 1][w1] + sum[h1][w1] == 0) || (sum[h2 + 1][w2] - sum[h1][w2] - sum[h2 + 1][w1] + sum[h1][w1] == (w2 - w1) * (h2 + 1 - h1)))) ++ h2;
                dp2[h1][w1][w2][0] = h2;
            }
        }
    }
    int res = 30;
    for(int k = 0; k + 1 <= 30; ++ k) {
        // check
        if(dp1[0][h][0][k % 2] == w) chmin(res, k);
        if(dp2[0][0][w][k % 2] == h) chmin(res, k);
        // 遷移
        // dp1
        for(int h1 = 0; h1 <= h; ++ h1) {
            for(int h2 = 0; h2 <= h; ++ h2) {
                for(int w1 = 0; w1 <= w; ++ w1) {
                    int w_ = dp1[h1][h2][w1][k % 2];
                    chmax(dp1[h1][h2][w1][(k + 1) % 2], dp1[h1][h2][w_][k % 2]);
                }
                int w2 = 0;
                for(int w1 = 0; w1 <= w; ++ w1) {
                    if(w2 < w1) w2 = w1;
                    int h_ = dp2[h1][w1][w2 + 1][k % 2];
                    while(w2 < w && dp2[dp2[h1][w1][w2+1][k%2]][w1][w2+1][k%2] >= h2) {
                        ++ w2;
                        h_ = dp2[h1][w1][w2 + 1][k % 2];
                    }
                    chmax(dp1[h1][h2][w1][(k + 1) % 2], w2);
                }
            }
        }
        //dp2
        for(int w1 = 0; w1 <= w; ++ w1) {
            for(int w2 = 0; w2 <= w; ++ w2) {
                for(int h1 = 0; h1 <= h; ++ h1) {
                    int h_ = dp2[h1][w1][w2][k % 2];
                    chmax(dp2[h1][w1][w2][(k + 1) % 2], dp2[h_][w1][w2][k % 2]);
                }
                int h2 = 0;
                for(int h1 = 0; h1 <= h; ++ h1) {
                    int w_ = dp1[h1][h2 + 1][w1][k % 2];
                    while(h2 < h && dp1[h1][h2+1][dp1[h1][h2+1][w1][k%2]][k%2] >= w2) {
                        ++ h2;
                        w_ = dp1[h1][h2 + 1][w1][k % 2];
                    }
                    chmax(dp2[h1][w1][w2][(k + 1) % 2], h2);
                }
            }
        }
        rep(x, 200) {
            rep(y, 200) {
                rep(z, 200) {
                    dp1[x][y][z][k % 2] = dp2[x][y][z][k % 2] = -1;
                }
            }
        }
    }
    cout << res << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 128852