#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long long ll;

const int inf = 1e9;
const ll inf64 = 1e18;

const int N = 190;

mt19937 rnd(42);

int n, m;
int mat[N][N];
int U[N][N][N], L[N][N][N], U2[N][N][N], L2[N][N][N];

void read() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            mat[i][j] = s[j] == '#';
        }
    }
}

void gen() {
    n = 18;
    m = 18;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mat[i][j] = int(rnd() % 2);
        }
    }
}

void print() {
    cout << n << " " << m << "\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << mat[i][j] << " ";
        }
        cout << "\n";
    }
}

int slow() {
    vector<vector<vector<vector<int>>>> dp(n, vector<vector<vector<int>>>(n, vector<vector<int>>(m, vector<int>(m))));
    vector<vector<int>> cnt(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cnt[i][j] = mat[i][j];
            if (i) cnt[i][j] += cnt[i - 1][j];
            if (j) cnt[i][j] += cnt[i][j - 1];
            if (i && j) cnt[i][j] -= cnt[i - 1][j - 1];
        }
    }
    auto get = [&](int li, int ri, int lj, int rj) -> int {
        int res = cnt[ri][rj];
        if (li) res -= cnt[li - 1][rj];
        if (lj) res -= cnt[ri][lj - 1];
        if (li && lj) res += cnt[li - 1][lj - 1];
        return res;
    };
    for (int li = n - 1; li >= 0; li--) {
        for (int ri = li; ri < n; ri++) {
            for (int lj = m - 1; lj >= 0; lj--) {
                for (int rj = lj; rj < m; rj++) {
                    int cc = get(li, ri, lj, rj);
                    if (cc == 0 || cc == (ri - li + 1) * (rj - lj + 1)) {
                        continue;
                    }
                    cc = 20;
                    for (int qi = li; qi < ri; qi++) {
                        cc = min(cc, max(dp[li][qi][lj][rj], dp[qi + 1][ri][lj][rj]) + 1);
                    }
                    for (int qj = lj; qj < rj; qj++) {
                        cc = min(cc, max(dp[li][ri][lj][qj], dp[li][ri][qj + 1][rj]) + 1);
                    }
                    dp[li][ri][lj][rj] = cc;
                }
            }
        }
    }
    return dp[0][n - 1][0][m - 1];
}

int fast() {

    fill((int*)U, (int*)U + N * N * N, 0);
    fill((int*)L, (int*)L + N * N * N, 0);

    for (int i = 0; i < n; i++) {
        for (int l = 0; l < m; l++) {
            for (int r = l; r < m; r++) {
                if (mat[i][r] != mat[i][l]) {
                    break;
                }
                if (i == 0) {
                    U[i][l][r] = 1;
                    continue;
                }
                if (mat[i - 1][l] == mat[i][l]) {
                    U[i][l][r] = 1 + U[i - 1][l][r];
                } else {
                    U[i][l][r] = 1;
                }
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                if (mat[r][i] != mat[l][i]) {
                    break;
                }
                if (i == 0) {
                    L[i][l][r] = 1;
                    continue;
                }
                if (mat[l][i] == mat[l][i - 1]) {
                    L[i][l][r] = 1 + L[i - 1][l][r];
                } else {
                    L[i][l][r] = 1;
                }
            }
        }
    }

    if (U[n - 1][0][m - 1] == n) {
        return 0;
    }

    for (int x = 0; ; x++) {

//        cout << "x = " << x << "\n";
//
//        for (int i = 0; i < n; i++) {
//            for (int l = 0; l < m; l++) {
//                for (int r = l; r < m; r++) {
//                    cout << "(" << i << ", " << l << ", " << r << ") = " << U[i][l][r] << "\n";
//                }
//            }
//        }
//
//        cout << "\n--------------\n";
//
//        for (int i = 0; i < m; i++) {
//            for (int l = 0; l < n; l++) {
//                for (int r = l; r < n; r++) {
//                    cout << "(" << i << ", " << l << ", " << r << ") = " << L[i][l][r] << "\n";
//                }
//            }
//        }
//
//        cout << "\n--------------\n";

        for (int l = 0; l < m; l++) {
            for (int r = l; r < m; r++) {
                for (int i = 0; i < n; i++) {
                    int k = U[i][l][r];
                    U2[i][l][r] = k + (i >= k ? U[i - k][l][r] : 0);
                }
            }
        }

        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                for (int i = 0; i < m; i++) {
                    int k = L[i][l][r];
                    L2[i][l][r] = k + (i >= k ? L[i - k][l][r] : 0);
                }
            }
        }

        memcpy((int*)U, (int*)U2, sizeof(int) * N * N * N);
        memcpy((int*)L, (int*)L2, sizeof(int) * N * N * N);

        for (int l = 0; l < m; l++) {
            for (int r = l; r < m; r++) {
                for (int ii = 0, i = 0; i < n; i++) {
                    while (ii <= i && L2[r][ii][i] < r - l + 1) {
                        ii++;
                    }
                    if (ii <= i) {
                        U[i][l][r] = max(U[i][l][r], i - ii + 1);
                    }
                }
            }
        }

        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                for (int ii = 0, i = 0; i < m; i++) {
                    while (ii <= i && U2[r][ii][i] < r - l + 1) {
                        ii++;
                    }
                    if (ii <= i) {
                        L[i][l][r] = max(L[i][l][r], i - ii + 1);
                    }
                }
            }
        }

        if (U[n - 1][0][m - 1] == n) {
            return x + 1;
        }
    }
}

void test() {
    while (1) {
        gen();
        int fs = fast();
        int sl = slow();
        if (fs == sl) {
            cout << "OK (" << fs << " == " << sl << ")\n";
            continue;
        }
        cout << "WA\n";
        cout << "exp = " << sl << "\n";
        cout << "fnd = " << fs << "\n";
        print();
        break;
    }
}

void work() {
    read();
    cout << fast() << "\n";
}

int main() {

#ifdef debug
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    work();
    // test();

    return 0;
}

Measured memory_bytes: 107648