import std.stdio, std.algorithm;

int n, m;
int[] xs, memo;

void main(){
	for(;scanf("%d%d\n", &m, &n) && n;){
		xs.length = n;
		foreach(ref x; xs){
			x = 0;
			auto s = readln;
			foreach(i; 0..m) x |= (s[i]=='1')<<i;
		}
		memo.length = 3^^m;
		memo[] = -1;
		writeln(solve(0));
	}
}

int solve(int state){
	if(memo[state] >= 0) return memo[state];
	int ans = int.max;
	scope(exit) memo[state] = ans;
	int checked = 0, info = 0;
	foreach(i; 0..m)if(state/(3^^i)%3){
		checked |= 1<<i;
		info |= (state/(3^^i)%3 == 1)<<i;
	}
	int cands = cast(int)count!(x=>(x&checked)==info)(xs);
	if(cands <= 1) return ans = 0;
	foreach(i; 0..m)if(state/(3^^i)%3 == 0)
		ans = min(ans, 1 + max(solve(state+(3^^i)*1), solve(state+(3^^i)*2)));
	return ans;
}