#include using namespace std; struct node{ int sz; list edge; node(){sz=1;}; }; bool check(int r,int c,int N,int M){ if(0<=r&&r>N>>M;N+=2,M+=2; vector grid(N); using VB=vector; using VVB=vector; VVB used(N,VB(M,false)); vector tree(1);tree[0].sz=0; for(int i = 0; i < M; i++)grid[0]+='.',grid[N-1]+='.'; for(int i=1;i>grid[i]; grid[i]="."+grid[i]+"."; } int D=0; std::function dfs=[&](int r,int c,int now){ D++; used[r][c]=true; stack> W; vector> X; W.push(mp(r,c)); while(W.empty()==false){ r=W.top().first;c=W.top().second;W.pop(); for(int i = 0; i < 4; i++){ int nr=r+dir4[i],nc=c+dir4[i+1]; if(check(nr,nc,N,M)&&used[nr][nc]==false){ used[nr][nc]=true; if(grid[nr][nc]=='.')W.push(mp(nr,nc)); else X.push_back(mp(nr,nc)); } } } for(auto& it : X){ r=it.first,c=it.second; used[r][c]=false; } for(auto& it : X){ r=it.first,c=it.second; if(used[r][c]==false){ tree[now].edge.push_back(tree.size()); tree.push_back(node()); W.push(mp(r,c)); used[r][c]=true; while(W.empty()==false){ r=W.top().first;c=W.top().second;W.pop(); grid[r][c]='0'+D; for(int i = 0; i < 8; i++){ int nr=r+dir8[i],nc=c+dir8[i+1]; if(check(nr,nc,N,M)&&used[nr][nc]==false&&grid[nr][nc]=='x'){ tree.back().sz++; used[nr][nc]=true; W.push(mp(nr,nc)); } } } for(int i = 0; i < 4; i++){ int nr=r+dir4[i],nc=c+dir4[i+1]; if(check(nr,nc,N,M)&&used[nr][nc]==false){ dfs(nr,nc,tree.size()-1); } } } } D--; }; dfs(0,0,0); int Z=tree.size(); vector> dp(Z,mp(0,0)); std::function dfs2=[&](int v){ dp[v].first=tree[v].sz; dp[v].second=0; for(auto& u : tree[v].edge){ dfs2(u); dp[v].first+=dp[u].second; dp[v].second+=max(dp[u].first,dp[u].second); } }; //for(auto& it : grid){cout << it << endl;} dfs2(0); cout<