#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
vi v;
int m, n;
short dp[1 << 12][1 << 12];

int solve(int asked, int resp)
{
	if (dp[asked][resp] >= 0) return dp[asked][resp];
	int cnt = 0;
	REP(i, n)
	{
		if ((v[i] & asked) == resp) cnt++;
	}
	int res = m;
	if (cnt <= 1)
	{
		res = 0;
	}
	else
	{
		REP(i, m)
		{
			int nx = asked | (1 << i);
			if (nx == asked) continue;
			chmin(res, max(solve(nx, resp | (1 << i)), solve(nx, resp))+1);
		}
	}
	return dp[asked][resp] = res;
}

int tonum(string s)
{
	int res = 0;
	REP(i, s.size())
	{
		res *= 2;
		res += s[i] - '0';
	}
	return res;
}

int main()
{
	while (cin >> m >> n, m)
	{
		MS(dp, -1);
		v.resize(n);
		REP(i, n)
		{
			string s;
			cin >> s;
			v[i] = tonum(s);
		}
		cout << solve(0, 0) << endl;
	}
	return 0;
}