3882번 - 스무고개

어떤 방에 n개의 물건이 있고, 각 물건은 특징을 가지고 있다. 각 특징은 예 또는 아니오로 대답할 수 있는 질문이다.

특징은 총 종류가 m개가 있다. 이러한 특징을 이용하면 이 방에 있는 모든 물건을 설명할 수 있다. 즉, 모든 물건은 길이가 일정한 불리언 수열로 나타낼 수 있다. 모든 물체는 다른 물체와 적어도 한 특징이 다르다.

상근이는 어떤 물체를 확인하려고 한다. 따라서, 그 물체의 특징을 알고 있는 사람에게 질문을 할 것이다. 모든 질문은 특징 중 하나이고, 모든 답변은 예 또는 아니오이다. 상근이는 답변을 들은 후에 다음 질문을 고를 수 있다.

상근이는 질문은 하나 할 때 마다 100원씩 내야 한다. 주머니 사정이 넉넉하지 않은 상근이는 돈을 가능한 적게 내려고 한다. 상근이는 모든 물체의 특징을 알고 있다. 하지만, 찾으려고 하는 물체의 특징은 알고 있지 못한다. 따라서, 상근이는 질문을 하기 전에 전략을 세울 수 있다.

물체의 특징이 주어졌을 때, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 특징의 개수 m과 물체의 개수 n이 주어진다. (0 < m ≤ 11, 0 < n ≤ 128) 다음 n개의 줄에는 각 물체의 특징이 주어진다. 특징은 길이가 m인 이진 문자열로 각 값은 1(예) 또는 0(아니오)이다. 두 물체의 특징이 같은 경우는 없다.

각 테스트 케이스에 대해서, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 출력한다. 가능한 질문을 적게 해야 한다.