use std::io::Read;

fn chmax<T: Ord>(x: &mut T, a: T) {
    if *x < a {
        *x = a;
    }
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let h: usize = it.next().unwrap().parse().unwrap();
    let w: usize = it.next().unwrap().parse().unwrap();
    let s: Vec<Vec<usize>> = (0..h)
        .map(|_| {
            it.next()
                .unwrap()
                .chars()
                .map(|c| (c == '#') as usize)
                .collect()
        })
        .collect();
    let mut sum = vec![vec![0; w + 1]; h + 1];
    for i in (0..h).rev() {
        for j in (0..w).rev() {
            sum[i][j] = sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1] + s[i][j];
        }
    }
    let only = |u: usize, d: usize, l: usize, r: usize| -> bool {
        let cnt = sum[u][l] + sum[d][r] - sum[u][r] - sum[d][l];
        cnt == 0 || cnt == (d - u) * (r - l)
    };
    let mut dp_row = vec![vec![vec![0u8; w + 1]; h + 1]; h + 1];// [上][下][左] = 右の最大
    let mut dp_col = vec![vec![vec![0u8; h + 1]; w + 1]; w + 1];// [左][右][上] = 下の最大
    for u in 0..h {
        for d in (u + 1)..(h + 1) {
            let mut r = w;
            for l in (0..w).rev(){
                while !only(u, d, l, r) {
                    r -= 1;
                }
                dp_row[u][d][l] = r as u8;
            }
            dp_row[u][d][w] = w as u8;
        }
    }
    for l in 0..w {
        for r in (l + 1)..(w + 1) {
            let mut d = h;
            for u in (0..h).rev(){
                while !only(u, d, l, r) {
                    d -= 1;
                }
                dp_col[l][r][u] = d as u8;
            }
            dp_col[l][r][h] = h as u8;
        }
    }
    let mut next_row = dp_row.clone();
    let mut next_col = dp_col.clone();
    for iteration in 0.. {
        if dp_row[0][h][0] == w as u8 {
            println!("{}", iteration);
            return;
        }
        for u in 0..h {
            for d in (u + 1)..(h + 1) {
                let row = &dp_row[u][d];
                for l in 0..w {
                    let r = row[row[l] as usize] as usize;
                    chmax(&mut next_row[u][d][l], r as u8);
                    chmax(&mut next_col[l][r][u], d as u8);
                }
            }
        }
        for l in 0..w {
            for r in (l + 1)..(w + 1) {
                let col = &dp_col[l][r];
                for u in 0..h {
                    let d = col[col[u] as usize] as usize;
                    chmax(&mut next_col[l][r][u], d as u8);
                    chmax(&mut next_row[u][d][l], r as u8);
                }
            }
        }
        std::mem::swap(&mut dp_row, &mut next_row);
        std::mem::swap(&mut dp_col, &mut next_col);
        for u in 0..h {
            for d in ((u + 1)..(h + 1)).rev() {
                for l in 0..w {
                    let dp = &mut dp_row;
                    let v = dp[u][d][l];
                    if u + 1 < d  {
                        chmax(&mut dp[u + 1][d][l], v);
                        chmax(&mut dp[u][d - 1][l], v);
                    }
                    chmax(&mut dp[u][d][l + 1], v);
                }
            }
        }
        for l in 0..w {
            for r in ((l + 1)..(w + 1)).rev() {
                for u in 0..h {
                    let dp = &mut dp_col;
                    let v = dp[l][r][u];
                    if l + 1 < r  {
                        chmax(&mut dp[l + 1][r][u], v);
                        chmax(&mut dp[l][r - 1][u], v);
                    }
                    chmax(&mut dp[l][r][u + 1], v);
                }
            }
        }
    }
}

fn main() {
    run();
}


Measured memory_bytes: 35068