#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++; vector s(h); s[0]=string(w,'.'); for(Int i=1;i>s[i]; Int n=h*w+1; UnionFind uf(n); auto idx=[&](Int i,Int j){return i*w+j;}; for(Int i=0;i=0&&j+1 > 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,h*w); 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'){ if(!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); } }else{ used[nz]=1; q.emplace(ny,nx); } } } } vector dp1(n),dp2(n); function dfs= [&](Int v)->void{ if(uf.r[v]>1) dp1[v]=uf.r[v]; for(Int u:G[v]){ //cout<"<