#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> E;
typedef long long LL;
string code[128];
int obj[128];
int m, n;
int memo[2048][2048];
int solve(int q, int a) {
	if (memo[q][a] != -1) return memo[q][a];
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if ((obj[i] & q) == a)cnt++;
	}
	if (cnt < 2) return memo[q][a] = 0;
	int ret = m;
	for (int i = 0; i < m; i++) {
		int nq = q | (1 << i);
		if (nq == q) continue;
		ret = min(ret, max(solve(nq, a | (1 << i)), solve(nq, a)) + 1);
	}
	return memo[q][a] = ret;
}
int main() {
	while (cin >> m >> n, m) {
		for (int i = 0; i < n; i++) cin >> code[i];
		memset(obj, 0, sizeof(obj));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (code[i][j] == '1') obj[i] |= (1 << j);
			}
		}
		memset(memo, -1, sizeof(memo));
		cout << solve(0, 0) << endl;
	}
}
