Twenty Questions

There are $n$ objects in a room, and each object is described by a set of features. Each feature corresponds to a question that can be answered only with "yes" or "no".

There are $m$ features in total, and these $m$ features are enough to tell every object in the room apart. In other words, each object is represented by a boolean (binary) sequence of length $m$, and any two distinct objects differ in at least one feature.

You want to figure out which one of the objects in the room a particular hidden object is. To do so, you ask questions to someone who knows all of that object's features. Every question has the form "Does this object have feature $j$?", and every answer is "yes" or "no". After hearing each answer, you may choose your next question.

Because each question costs 100 won, you want to ask as few questions (and thus pay as little) as possible. You know the features of every object in the room, but you do not know which of them is the hidden object, so you may plan a strategy (the order of questions and how to branch on the answers) before you start asking.

Assuming you use the best possible strategy, write a program that finds the minimum number of questions that is guaranteed to identify any object in the worst case.

The input consists of several test cases.

The first line of each test case contains the number of features $m$ and the number of objects $n$ ($0 < m \le 11$, $0 < n \le 128$). Each of the next $n$ lines describes one object's features as a binary string of length $m$, where each position is 1 (yes) or 0 (no). No two objects have exactly the same features.

For each test case, print on its own line the minimum number of questions needed, in the worst case, to distinguish any object when using the best possible strategy.