#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#define INF 1<<10
using namespace std;

int n,m;
int dp[1<<12][1<<12];
int data[150];
vector<int> dif;

int memo(int used,int yn){
	if(dp[used][yn]!=INF)return dp[used][yn];
	int cnt=0;
	for(int i=0;i<n;i++){
		if((used&data[i])==yn)cnt++;
	}
	if(cnt<=1)return dp[used][yn]=0;
	int res=INF;
	for(int i=0;i<m;i++){
		if(used>>i & 1)continue;
		res=min(res,max(memo(used|(1<<i),yn),memo(used|(1<<i),yn|(1<<i))));
	}
	return dp[used][yn]=(res+1);
}

int main(void){
	while(1){
		scanf("%d%d",&m,&n);
		if(n+m==0)break;
		memset(data,0,sizeof(data));
		for(int i=0;i<n;i++){
			string str;
			cin >> str;
			for(int j=0;j<m;j++){
				if(str[j]=='1')data[i]+=(1<<j);
			}
		}
		for(int i=0;i<(1<<m);i++){
			for(int j=0;j<(1<<m);j++){
				dp[i][j]=INF;
			}
		}
		printf("%d\n",memo(0,0));
	}
	return 0;
}