|
|
 #include <iostream>
using namespace std;
const int maxn=1025;
const int maxm=100000;
struct gtype
   {
 int x,y,next;
 };
gtype g[maxm];
int first[maxn];
int link[maxn];
bool used[maxn];
int f2[11]={1,2,4,8,16,32,64,128,256,512,1024};
bool in[1025];
int cheese[1025];
int n,m,tot;
int i,j,all;
void add(int x,int y)
{
tot++;
g[tot].x=x;g[tot].y=y;
g[tot].next=first[x];
first[x]=tot;
}
bool find(int s)
{
int temp=first[s];
while(temp!=-1)
  {
int e=g[temp].y;
if(!used[e])
{
used[e]=true;
if(link[e]==0||find(link[e]))
{
link[e]=s;
return 1;
 }
}
temp=g[temp].next;
}
return 0;
}
int match()
{
int sum=0;
for(i=0;i<all;i++)
{
memset(used,0,sizeof(used));
sum+=find(i);
}
return sum;
}
bool check(int a,int b)
{
int t=cheese[a]^cheese[b];
return t&&(t&(t-1))==0;
}
int main()
{
while(cin>>n>>m)
{
if(n==0&&m==0) break;
memset(first,-1,sizeof(first));
memset(link,0,sizeof(link));
char s;
for(i=0;i<m;i++)
{
int flag=-1;
int t=0;
for(j=0;j<n;j++)
{
cin>>s;
if(s=='*')
{
flag=j;
continue;
}
t+=(s-'0')*f2[j];
}
in[t]=true;
if(flag!=-1)
in[t+f2[flag]]=true;
}
all=0;
for(i=0;i<(1<<n);i++)
if(in[i])
cheese[all++]=i;
for(i=0;i<all;i++)
for(j=0;j<all;j++)
{
if(i==j) continue;
if(check(i,j))
add(i,j);
}
int ans=all-match()/2;
cout<<ans<<endl;
}
return 0;
}
|