#include <bits/stdc++.h>
using namespace std;





int pow3[12] = {1}, n, m;

int dp[177147], cnt[177147];


int edcode(vector<int> S) {
  int ans = 0;
  for (int i = 0; i < 11; ++i) {
    ans += S[i] * pow3[i];
  }
  return ans;
}

vector<int> decode(int S) {
  vector<int> ans;
  for (int i = 0; i < 11; ++i, S /= 3) {
    ans.push_back(S % 3);
  }
  return ans;
}

int dfs(int S) {
  if (dp[S] != -1) return dp[S];
  else if (cnt[S] == 1) return 0;
  else {
    auto c = decode(S);
    dp[S] = INT_MAX;
    for (int i = 0; i < m; ++i) {
      if (c[i] == 2) {
        dp[S] = min(dp[S], 1 + max(dfs(S - pow3[i]), dfs(S - 2 * pow3[i])));
      }
    }
    return dp[S];
  }
}



int main() {
  for (int i = 1; i < 12; ++i) pow3[i] = pow3[i - 1] * 3;
  ios_base::sync_with_stdio(false); cin.tie(0);
  while (cin >> m >> n and n) {
    vector<int> A;

    for (int i = 0; i < n; ++i) {
      string s; cin >> s;
      int ans = 0;
      for (int i = 0; i < m; ++i) {
        ans |= (s[i] - '0')<<i;
      }
      A.emplace_back(ans);
    }
    fill(dp, dp + pow3[m], -1);

    for (int S = 0; S < pow3[m]; ++S) {
      vector<int> c = decode(S);
      cnt[S] = 0;
      for (int i = 0; i < n; ++i) {
        bool test = true;
        for (int j = 0; j < m and test; ++j) {
          test &= c[j] == 2 or c[j] == ((A[i]>>j)&1);
        }
        cnt[S] += test;
      }
    }
    cout << dfs(pow3[m] - 1) << '\n';
  }
}

