import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

void main() {
    int M, N;
    string[] F;
    bool input() {
        scanf("%d %d\n", &M, &N);
        if (M == 0 && N == 0) return false;
        F = new string[N];
        foreach (i; 0 .. N) {
            F[i] = readln.chomp;
        }
        return true;
    }
    int tobinary(in string s) {
        char[] t = cast(char[])(s.dup);
        int Ret = 0;
        t.reverse;
        foreach (i; 0 .. t.length) {
            Ret += ((t[i] == '1' ? 1 : 0) << i);
        }
        return Ret;
    }
    void solve() {
        int[] G = new int[N];
        foreach (i; 0 .. N) {
            G[i] = tobinary(F[i]);
        }
        int INF = int.max / 2;
        auto memo = new int[][](1 << M, 1 << M);
        foreach (i; 0 .. (1 << M)) memo[i][] = -1;
        int dfs(int used, int gid) {
            int C = 0;
            if (memo[used][gid] >= 0) return memo[used][gid];
            foreach (i; 0 .. N) {
                if ((G[i] & used) == gid) {
                    C++;
                }
            }
            if (C == 0) return INF;
            if (C == 1) return 0;
            int Ret = INF;
            foreach (i; 0 .. M) {
                if (used & (1 << i)) continue;
                int x = dfs(used | 1 << i, gid);
                int y = dfs(used | 1 << i, gid | 1 << i);
                //writeln([x, y]);
                Ret = min(Ret, max(x, y) + 1);
            }
            static if (false){ 
                writeln("C: ", C, 
                    " used: ", format("%0" ~ M.to!string ~ "b", used),
                    " gid: ", format("%0" ~ M.to!string ~ "b", gid),
                    " --> ", Ret);
            }
            return memo[used][gid] = Ret;
        }
        writeln(dfs(0, 0));
    }
    while (input) solve;
}