#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007LL;
int m, n;
int po[13] = {};

void init(){
    po[0] = 1;
    for(int i = 1; i < 13; i++) po[i] = po[i - 1] * 3;
}

int dfs(vector<string> &data, vector<int> &dp, int S){
    
    int ret = dp[S];
    if(ret != MOD) return ret;
    string state = "";
    int temp_S = S;
    for(int i = 0; i < m; i++){
        string add = "";
        if(S % 3 == 0) add = "0";
        else if(S % 3 == 1) add = "1";
        else add = "2";
        
        state = add + state;
        S /= 3;
    }

    //cout << "state is " << state << endl;
    //残っている data の数
    int cnt = 0;
    
    for(int i = 0; i < n; i++){
        bool ok = true;
        for(int j = 0; j < m; j++){
            if(state[j] == '2') continue;
            if(data[i][j] != state[j]) ok = false;
        }
        cnt += ok;
    }

    if(cnt <= 1){
        ret = 0;
        dp[S] = ret;
        //cout << "dp[" + state + "] = " << dp[S] << endl;        
        return ret;
    }

    // 未決定 (2) のところを 0 or 1 に変更して遷移する
    S = temp_S;
    
    for(int i = 0; i < m; i++){
        if(state[i] == '2'){
            int T1 = S + po[m - i - 1] * (0 - 2);
            int T2 = S + po[m - i - 1] * (1 - 2);
            //cout << S << " " << state << " " << T1 << " " << T2 << endl;
            int temp = max(dfs(data, dp, T1), dfs(data, dp, T2)) + 1;
            ret = min(ret, temp);
        }
    }

    dp[S] = ret;
    //cout << "dp[" + state + "] = " << dp[S] << endl;            
    return ret;
}

signed main(){

    init();

    while(1){
        cin >> m >> n;
        if(n == 0) break;
        vector<string> data(n);
        for(int i = 0; i < n; i++) cin >> data[i];

        int S = (int)po[m] - 1;

        // 状態 S を特定するために必要な最大の質問回数
        vector<int> dp(S + 1, MOD);
        cout << dfs(data, dp, S) << endl;
    }

    return 0;
}
