#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a r,p; UnionFind(){} UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);} Int find(Int x){ return (x==p[x]?x:p[x]=find(p[x])); } bool same(Int x,Int y){ return find(x)==find(y); } void unite(Int x,Int y){ x=find(x);y=find(y); if(x==y) return; if(r[x]>h>>w; h++;w+=2; vector s(h); s[0]=string(w,'.'); s[h++]=string(w,'.'); for(Int i=1;i>s[i],s[i]='.'+s[i]+'.'; Int n=h*w; UnionFind uf(n); auto idx=[&](Int i,Int j){return i*w+j;}; for(Int i=0;i=0&&j+1 ss; for(Int i=0;i1); vector > G(n); vector sz(n); Int dy[]={0,0,1,-1}; Int dx[]={1,-1,0,0}; vector used(n,0); auto in=[&](Int y,Int x){return 0<=y&&y; queue qt; qt.emplace(0,0,uf.find(0)); while(!qt.empty()){ Int sy,sx,c; tie(sy,sx,c)=qt.front();qt.pop(); using P = pair; queue

q; used[idx(sy,sx)]=1; q.emplace(sy,sx); while(!q.empty()){ Int y,x; tie(y,x)=q.front();q.pop(); for(Int k=0;k<4;k++){ Int ny=y+dy[k],nx=x+dx[k]; Int nz=idx(ny,nx); if(!in(ny,nx)||used[nz]) continue; if(s[ny][nx]=='x'&&!uf.same(c,nz)){ G[c].emplace(uf.find(nz)); qt.emplace(ny,nx,uf.find(nz)); }else{ used[nz]=1; q.emplace(ny,nx); } } } } vector dp1(n,0),dp2(n,0); function dfs= [&](Int v)->void{ dp1[v]=uf.r[v]; for(Int u:G[v]){ dfs(u); dp1[v]+=dp2[u]; dp2[v]+=dp1[u]; } chmax(dp1[v],dp2[v]); }; dfs(0); cout<