class in{struct It{int it;const bool rev;explicit constexpr It(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(It& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const It i,n;public:explicit constexpr in(int n):i(0),n(n<0?0:n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const It& begin(){return i;}const It& end(){return n;}};
 
#include <iostream>
#include <vector>
#include <string>
#include <functional>
using namespace std;
const int INF = 1e9;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    while(cin >> n >> m && n) {
        vector<int> t(m);
        for(int& x : t) {
            string s;
            cin >> s;
            int k = 1;
            for(char c : s)
                x += (c - '0') * k, k *= 2;
        }
        vector<vector<int>> dp(1 << n, vector<int>(1 << n, -1));
        function<int(int, int)> dfs = [&](int s1, int s2) {
            int& res = dp[s1][s2];
            if(res != -1) return res;
            res = INF;
            int cnt = 0;
            for(int x : t) if((s1 & x) == s2) ++cnt;
            if(cnt <= 1) return res = 0;
            for(int i : in(n)) {
                if((1 << i) & s1) continue;
                int ns = s1 | (1 << i);
                res = min(res, max(dfs(ns, s2 | (1 << i)), dfs(ns, s2)) + 1);
            }
            return res;
        };
        
        cout << dfs(0, 0) << endl;
    }
    return 0;
}