#include <bits/stdc++.h> #define PII pair<int,int> #define LL long long using namespace std; const int MOD=1e9+7; struct Moyun { int x,y; }a[105],b[105],c[105]; int N,M,A,B; int d[105]; char s[15][15]; bool okx[15],oky[15],vx[15],vy[15]; bool flag=0; bool vis[105],mark[105]; bool no=0; int fac[105],del[105]; int C=0,siz=0; vector<int>G[105]; void Check(int u,int fa) { // printf("Check%d %d\n",u,fa); int S=0; if(mark[u]==1) { no=1; return; } mark[u]=1,siz++; if(no) return; for(int v:G[u]) { if(v==fa) continue; Check(v,u); if(!del[v]) S++; } if(S==0||S==2) return; if(S==1) { del[u]==1; return; } no=1; return; } int ans=-1; void dfs1(int p) { if(flag) return; if(p>10||ans!=-1&&p>=ans) return; for(int i=1;i<=N+M;i++) G[i].clear(),del[i]=1; int C=A+p; for(int i=1;i<=C;i++) G[c[i].x].push_back(c[i].y+N),G[c[i].y+N].push_back(c[i].x); for(int i=1;i<=N+M;i++) mark[i]=0; // for(int i=1;i<=C;i++) printf("(%d %d)",c[i].x,c[i].y); // puts(""); no=0,siz=1; for(int i=1;i<=N+M;i++) { if(mark[i]) continue; // puts("Start!"); Check(i,-1); // puts("End!"); if(siz&1) { no=1; break; } siz=1; } if(!no) { flag=1; if(ans==-1) ans=p; else ans=min(ans,p); return; } for(int i=1;i<=B;i++) { if(vis[i]||vx[b[i].x]||vy[b[i].y]) continue; c[A+p+1]=b[i]; vx[b[i].x]=vy[b[i].y]=1; vis[i]=1; dfs1(p+1); vx[b[i].x]=vy[b[i].y]=0; vis[i]=0; } return; } int main() { //freopen("c.in","r",stdin); //freopen("c.out","w",stdout); scanf("%d %d",&N,&M); for(int i=1;i<=N;i++) { scanf("%s",s[i]+1); for(int j=1;j<=M;j++) { if(s[i][j]=='#') okx[i]=oky[j]=1,a[++A]={i,j}; } } for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if((okx[i]||oky[j])&&s[i][j]=='.') b[++B]={i,j}; fac[1]=1; for(int i=2;i<=10;i++) fac[i]=fac[i-1]*i; // puts("^_^"); for(int i=1;i<=A;i++) c[i]=a[i]; dfs1(0); printf("%d\n",ans); return 0; }