#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}

int h,w;
vector<string> s;
unsigned char dp[186][186][186][36];
unsigned char dp2[186][186][186][36];
int sm[186][186];
bool calc(int a,int b,int c,int d){
    int res = sm[c+1][d+1] - sm[a][d+1] - sm[c+1][b] + sm[a][b];
    
    if(res !=(c-a+1)*(d-b+1)&&res!=0)return false;
    return true;
}
int main(){
    cin >> h >> w;
    s.resize(h);
    rep(i,h)cin >> s[i];
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#'){
                sm[i+1][j+1]++;
            }
        }
    }
    rep(i,h){
        rep(j,w){
            if(j!=0){
                sm[i+1][j+1] += sm[i+1][j];
            }
        }
    }
    rep(j,w){
        rep(i,h){
            if(i!=0){
                sm[i+1][j+1] += sm[i][j+1];
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=j;k<w;k++){
                int ok = i-1;
                int ng = h;
                while(ng-ok > 1){
                    int mid = (ok+ng)/2;
                    if(calc(i,j,mid,k)){
                        ok = mid;
                    }else{
                        ng = mid;
                    }
                }
                if(ok==i-1){
                    ok = -1;
                }
                ok++;
                dp[i+1][j+1][k+1][0] = (unsigned char)ok;
            }
        }
    }
    for(int j=0;j<w;j++){
        for(int i=0;i<h;i++){
            for(int k=i;k<h;k++){
                int ok = j-1;
                int ng = w;
                while(ng-ok > 1){
                    int mid = (ok+ng)/2;
                    if(calc(i,j,k,mid)){
                        ok = mid;
                    }else{
                        ng = mid;
                    }
                }
                if(ok==j-1){
                    ok = -1;
                }
                ok++;
                dp2[j+1][i+1][k+1][0] = (unsigned char) ok;
                
            }
        }
    }
    for(int x=0;x<35;x++){
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                for(unsigned char k=j;k<=w;k++){
                    chmax(dp[i][j][k][x+1],dp[i][j][k][x]);
                    if(dp[i][j][k][x]!=0){
                        unsigned char nx = dp[i][j][k][x];
                        chmax(dp[i][j][k][x+1],nx);
                        if(nx==h||nx==0)continue;
                        if(dp[nx+1][j][k][x]!=0){
                            unsigned char dd = dp[nx+1][j][k][x];
                            chmax(dp[i][j][k][x+1],dd);
                            for(int ss = i;ss <=dd;ss++){
                                chmax(dp2[j][i][ss][x+1],k);    
                            }
                            chmax(dp2[j][i][dd][x+1],k);
                        }
                    }
                    
                }
            }
        }
        for(int i=1;i<=w;i++){
            for(int j=1;j<=h;j++){
                for(unsigned char k=j;k<=h;k++){
                    chmax(dp2[i][j][k][x+1],dp2[i][j][k][x]);
                    if(dp2[i][j][k][x]!=0){
                        unsigned char nx = dp2[i][j][k][x];
                        chmax(dp2[i][j][k][x+1],nx);
                        if(nx==w||nx==0)continue;
                        if(dp2[nx+1][j][k][x]!=0){
                            unsigned char dd = dp2[nx+1][j][k][x];
                            chmax(dp2[i][j][k][x+1],dd);
                            for(int ss = i;ss <=dd;ss++){
                                chmax(dp[j][i][ss][x+1],k);    
                            }
                            chmax(dp[j][i][dd][x+1],k);
                        }
                    }
                }
            }
        }
    }
    // rep(i,h){
    //     rep(j,w){
    //         for(int k=j;k<w;k++){
    //             for(int x = 0;x<10;x++){
    //                 cout << i+1 << " " << j+1 << " " << k+1 << " " << x << ":1 " << (int)dp[i+1][j+1][k+1][x] << endl;
    //                 cout << i+1 << " " << j+1 << " " << k+1 << " " << x << ":2 " << (int)dp2[i+1][j+1][k+1][x] << endl;
    //             }
    //         }
    //     }
    // }

    for(int i=0;i<=35;i++){
        if((int)dp[1][1][w][i]==h){
            cout << i << endl;
            return 0;
        }
    }
    assert(0);
    return 0;
}

Measured memory_bytes: 451456