//
//  main.cpp
//  H
//
//  Created by 譚?髣サ霎セ on 15/2/24.
//  Copyright (c) 2015蟷エ 譚?髣サ霎セ. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>

int n,m,a,b[130],dp[2100][2100],v[15];
int dfs(int s1,int s2){
    if(dp[s1][s2]!=dp[2099][2099])return dp[s1][s2];
    int cnt=0;
    for(int i=0;i<m;i++)
        if((b[i]&s1)==s2)cnt++;
    if(cnt<=1)dp[s1][s2]=0;
    else{
        for(int i=0;i<n;i++)
            if(!(s1&v[i]))
                dp[s1][s2]=std::min(dp[s1][s2],std::max(dfs(s1|v[i],s2),dfs(s1|v[i],s2^v[i]))+1);
    }
    return dp[s1][s2];
}

int main(int argc, const char * argv[]) {
    
    for(int i=0;i<15;i++)v[i]=1<<i;
    while(scanf("%d%d",&n,&m)){
        if(!n && !m)break;
        memset(dp,10,sizeof(dp));
        for(int i=0;i<m;i++){
            b[i]=0;
            for(int j=0;j<n;j++){
                scanf("%1d",&a);
                if(a==1)b[i]|=v[j];
            }
        }
        printf("%d\n",dfs(0,0));
    }
    return 0;
}