#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

const int MAX = 190;
int dp1[MAX][MAX][MAX][2];
int dp2[MAX][MAX][MAX][2];

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> A(H);
  rep(i, H) cin >> A[i];
  vector<vector<int>> sum(H+1, vector<int>(W+1));
  rep(i, H) rep(j, W)
    sum[i+1][j+1] = sum[i+1][j]+sum[i][j+1]-sum[i][j]+(int)(A[i][j] == '#'); //二次元累積和
  
  auto isMono = [&](int u, int d, int l, int r) { 
    if(sum[d][r]-sum[u][r]-sum[d][l]+sum[u][l] == 0 || sum[d][r]-sum[u][r]-sum[d][l]+sum[u][l] == (d-u)*(r-l))
      return true;
    return false;
  };
  
  rep(u, H+1) {
    for(int d=u; d<=H; d++) {
      int r = 0;
      rep(l, W+1) {
        if(r < l) r = l;
        while(r < W && isMono(u, d, l, r+1)) //rを増やしていいのかを判定するためr+1とする
          r++;
        dp1[u][d][l][0] = r; //上下左を固定したときに長方形が1色になるr(右)の最大値
      }
    }
  }
  rep(l, W+1) {
    for(int r=l; r<=W; r++) {
      int d = 0;
      rep(u, H+1) {
        if(d < u) d = u;
        while(d < H && isMono(u, d+1, l, r)) //dを増やしていいのかを判定するためd+1とする
          d++;
        dp2[u][l][r][0] = d; //上左右を固定したときに長方形が1色になるd(下)の最大値
      }
    }
  }
  if(isMono(0, H, 0, W)) {
    cout << 0 << endl;
    return 0;
  }
  int ans = 20;
  for(int i=1; i<20; i++) {
    rep(u, H+1) {
      for (int d=u; d<=H; d++) {
        //縦に割る
        rep(l, W+1) {
          int l2 = dp1[u][d][l][(i-1)%2]; //複雑さi-1以下の長方形を(横に)2つ繋げると複雑さiの長方形になる
          chmax(dp1[u][d][l][i%2], dp1[u][d][l2][(i-1)%2]);
        }
        //横に割る
        int r = 0;
        rep(l, W+1) {
          if(r < l)
            r = l;
          int u2 = dp2[u][l][r+1][(i-1)%2]; //この線で横に分割できるか判定する
          while (r < W && dp2[u2][l][r+1][(i-1)%2] >= d) { //分割前の長方形の下辺がd以上であれば複雑さi-1に分割できる
            r++;
            u2 = dp2[u][l][r+1][(i-1)%2];
          }
          chmax(dp1[u][d][l][i%2], r); //元の長方形の複雑さはi
        }
      }
    }
    rep(l, W+1) {
      for (int r=l; r<=W; r++) {
        //横に割る
        rep(u, H+1) {
          int u2 = dp2[u][l][r][(i-1)%2]; //複雑さi-1以下の長方形を(縦に)2つ繋げると複雑さiの長方形になる
          chmax(dp2[u][l][r][i%2], dp2[u2][l][r][(i-1)%2]);
        }
        //縦に割る
        int d = 0;
        rep(u, H+1) {
          if(d < u)
            d = u;
          int l2 = dp1[u][d+1][l][(i-1)%2]; //この線で縦に分割できるか判定する
          while (d < H && dp1[u][d+1][l2][(i-1)%2] >= r) { //分割前の長方形の右辺がr以上であれば複雑さi-1に分割できる
            d++;
            l2 = dp1[u][d+1][l][(i-1)%2];
          }
          chmax(dp2[u][l][r][i%2], d); //元の長方形の複雑さはi
        }
      }
    }
    if(dp1[0][H][0][i%2] == W || dp2[0][0][W][i%2] == H) {
      ans = i;
      break;
    }
    rep(x, MAX) rep(y, MAX) rep(z, MAX)
      dp1[x][y][z][(i-1)%2] = dp2[x][y][z][(i-1)%2] = 0; //使い終わったデータを消して配列を再利用する(メモリの節約)
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 107776