#include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int H,W; string S[1010]; template class UF { public: vector par,rank,cnt; UF() {par=rank=vector(um,0); cnt=vector(um,1); for(int i=0;irank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<1010101> uf; vector C[1010*1010]; vector G[1010*1010]; int vis[1010*1000]; int dp[1010*1000][2]; void dfs(int c,int ph) { int sy=c/W; int sx=c%W; vis[sy*W+sx]=1; int i,tx,ty; FORR(r,G[sy*W+sx]) { int cy=r/W,cx=r%W; for(ty=max(0,cy-1);ty<=min(cy+1,H-1);ty++) for(tx=max(0,cx-1);tx<=min(cx+1,W-1);tx++) if(vis[uf[ty*W+tx]]==0) { dfs(uf[ty*W+tx],1-ph); if(ph==0) { C[sy*W+sx].push_back(uf[ty*W+tx]); } else { FORR(r2,C[uf[ty*W+tx]]) C[sy*W+sx].push_back(r2); } } } } int dfs2(int r) { dp[r][1]=uf.count(r); FORR(r2,C[r]) { dfs2(r2); dp[r][0]+=max(dp[r2][0],dp[r2][1]); dp[r][1]+=dp[r2][0]; } return max(dp[r][0],dp[r][1]); } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; FOR(y,H) { cin>>S[y+1]; S[y+1]="."+S[y+1]+"."; } H+=2; W+=2; S[0]=string(W,'.'); S[H-1]=string(W,'.'); FOR(y,H) FOR(x,W) { if(S[y][x]=='.') { for(i=-1;i<=1;i++) for(j=-1;j<=1;j++) if(i==0 || j==0) if(y+i>=0 && y+i=0 && x+j=0 && y+i=0 && x+j