#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <map>
#include <set>
using namespace std;

int n, m;
int Q[128];
int dp[1 << 11][1 << 11];

int dfs(int S, int T) {
	if(dp[S][T] != -1) return dp[S][T];
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if((Q[i] & S) == T) cnt++;
	}
	if(cnt <= 1) return 0;

	int ret = m;
	for(int i = 0; i < m; i++) {
		if(S >> i & 1) continue;
		int a = 0;
		a = max(a, 1 + dfs(S | (1 << i), T));
		a = max(a, 1 + dfs(S | (1 << i), T | (1 << i)));
		ret = min(ret, a);
	}
	return dp[S][T] = ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while(cin >> m >> n, n | m) {
		for(int i = 0; i < n; i++) {
			Q[i] = 0;
			for(int j = 0; j < m; j++) {
				char c;
				cin >> c;
				if(c == '1') Q[i] |= 1 << j;
			}
		}
		memset(dp, -1, sizeof dp);
		cout << dfs(0, 0) << endl;
	}
}