import random import heapq from collections import defaultdict,deque import sys readline=sys.stdin.readline class UnionFind: def __init__(self,n): self.n=n self.parents=[-1]*n def Find(self,x): stack=[] while self.parents[x]>=0: stack.append(x) x=self.parents[x] for y in stack: self.parents[y]=x return x def Union(self,x,y): x=self.Find(x) y=self.Find(y) if x==y: return if self.parents[x]>self.parents[y]: x,y=y,x self.parents[x]+=self.parents[y] self.parents[y]=x def Size(self,x): return -self.parents[self.Find(x)] def Same(self,x,y): return self.Find(x)==self.Find(y) def Members(self,x): root = self.Find(x) return [i for i in range(self.n) if self.Find(i)==root] def Roots(self): return [i for i, x in enumerate(self.parents) if x<0] def Group_Count(self): return len(self.Roots()) def All_Group_Members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.Find(member)].append(member) return group_members def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.All_Group_Members().items()) class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False): self.V=V self.directed=directed self.weighted=weighted if not graph: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) else: self.graph=graph self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) def SS_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V finished=[False]*self.V if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if parents or cycle_detection or subtree_size: ps=[None]*self.V ps[s]=s if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[float('inf')]*self.V uwd[s]=0 if weighted_dist: wd=[float('inf')]*self.V wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc.append(x) if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if parents or cycle_detection or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if type(uwd[i])==float or type(uwd[j])==float: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if type(uwd[x])==float: continue bg[uwd[x]%2].append(x) tpl=() if bipartite_graph: tpl+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) tpl+=(cd,) if directed_acyclic: tpl+=(dag,) if euler_tour: tpl+=(et,) if linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if postorder: tpl+=(post,) if preorder: tpl+=(pre,) if subtree_size: tpl+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] tpl+=(tp_sort,) if unweighted_dist: tpl+=(uwd,) if weighted_dist: tpl+=(wd,) if len(tpl)==1: tpl=tpl[0] return tpl def AP_DFS(self,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,topological_sort=False): seen=[False]*self.V finished=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if parents or cycle_detection: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] for s in range(self.V): if seen[s]: continue if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([]) if parents: ps[s]=s stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc[-1].append(x) if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if parents or cycle_detection: ps[y]=x elif not finished[y]: if directed_acyclic and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if postorder or topological_sort: post.append(x) if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) tpl=() if bipartite_graph: tpl+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) tpl+=(cd,) if directed_acyclic: tpl+=(dag,) if euler_tour: tpl+=(et,) if linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if postorder: tpl+=(post,) if preorder: tpl+=(pre,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] tpl+=(tp_sort,) if len(tpl)==1: tpl=tpl[0] return tpl def Build_Hash(self,s,random_number=False,mod=False,rerooting=False): self.bottom_hash=[None]*self.V if random_number: self.hash_random_number=random_number else: self.hash_random_number=[random.randint(1,10**10) for i in range(self.V)] if mod: self.hash_mod=mod else: self.hash_mod=(1<<61)-1 parents,postorder,preorder=self.SS_DFS(s,parents=True,postorder=True,preorder=True) for x in postorder: level=0 for y in self.graph[x]: if y==parents[x]: continue h,l=self.bottom_hash[y] level=max(level,l+1) ha=1 for y in self.graph[x]: if y==parents[x]: continue h,l=self.bottom_hash[y] ha*=h+self.hash_random_number[l] ha%=self.hash_mod self.bottom_hash[x]=(ha,level) if rerooting: self.top_hash=[None]*self.V self.top_hash[s]=(1,0) for x in preorder: children=[y for y in self.graph[x] if y!=parents[x]] if children: l=len(children) l_lst,r_lst=[None]*(l+1),[None]*(l+1) l_lst[0],r_lst[l]=(1,-1),(1,-1) for i in range(1,l+1): h0,l0=l_lst[i-1] h1,l1=self.bottom_hash[children[i-1]] l_lst[i]=(h0*(h1+self.hash_random_number[l1])%self.hash_mod,max(l0,l1)) for i in range(l-1,-1,-1): h0,l0=r_lst[i+1] h1,l1=self.bottom_hash[children[i]] r_lst[i]=(h0*(h1+self.hash_random_number[l1])%self.hash_mod,max(l0,l1)) for i in range(l): if x==s: ha,level=1,0 else: ha,level=self.top_hash[x] h0,l0=l_lst[i] h1,l1=r_lst[i+1] ha*=h0*h1 level=max(level,l0+1,l1+1) ha+=self.hash_random_number[level] ha%=self.hash_mod level+=1 self.top_hash[children[i]]=(ha,level) return def Hash(self,root,subtree=False): if subtree: ha,level=self.bottom_hash[root] ha+=self.hash_random_number[level] ha%=self.hash_mod else: h0,l0=self.bottom_hash[root] h1,l1=self.top_hash[root] ha=(h0*h1+self.hash_random_number[max(l0,l1)])%self.hash_mod level=max(l0,l1) return ha,level N,M=map(int,readline().split()) grid=["."*(M+2)]+["."+readline().rstrip()+"." for i in range(N)]+["."*(M+2)] N+=2;M+=2 UF=UnionFind(N*M) for n in range(N): for m in range(M): for dn,dm in ((0,1),(1,0)): if 0<=n+dn