#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <fstream>
#include <map>
#include <cstring>
#include <vector>

using namespace std;

int n,m;
string bits[1001];
const int INF=1000000000;


//bitset<int> nums[1<<11];
map<set<int>,int> sets;
int id;
map<int,int> dp[1<<11];
//map<set<int>,int > dp[1<<11];

// »ÝgÁ½¿âA»Ì¿âÉæÁÄ¾çê½ªÌ¤¿AÇÌªð©Ä¢é©AÅ»
int dfs(int s,int pos,set<int> &si,int sel){
	// WÌTCYª1Èº
	if(si.size()<=1)return 0;
	if(s==(1<<m)-1)return INF;
	if(sets.find(si)==sets.end())
		sets[si]=id++;
	if(dp[s].find(sets[si])!=dp[s].end())return dp[s][sets[si]];
	int res=INF;
	// ÇÌ¿âðg¤©
	for(int i=0;i<m;i++){
		// ·ÅÉgpÏÝ
		if((s>>i)&1)continue;
		// ªðs¤
		set<int> si1,si2;
		for(set<int>::iterator it=si.begin();it!=si.end();it++){
			int idx=*it;
			if(bits[idx][i]=='1')si1.insert(idx);
			else si2.insert(idx);
		}
		res=min(res,max(dfs(s|(1<<i),i,si1,0),dfs(s|(1<<i),i,si2,1))+1);
	}
	return dp[s][sets[si]]=res;
}

int main(){
	while(cin>>m>>n&&!(m==0&&n==0)){
		//memset(dp,-1,sizeof(dp));
		for(int i=0;i<(1<<11);i++)dp[i].clear();
		sets.clear();
		id=0;
		//for(int i=0;i<(1<<11);i++)
			//nums[i]=i;
		for(int i=0;i<n;i++)cin>>bits[i];
		set<int> init;
		for(int i=0;i<n;i++)init.insert(i);
		int res=INF;
		res=dfs(0,0,init,0);
		cout<<res<<endl;
	}
	return 0;
}