結果
問題 | No.1244 Black Segment |
ユーザー |
![]() |
提出日時 | 2023-03-22 00:25:22 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 441 ms / 2,000 ms |
コード長 | 60,341 bytes |
コンパイル時間 | 214 ms |
コンパイル使用メモリ | 18,432 KB |
実行使用メモリ | 61,952 KB |
最終ジャッジ日時 | 2024-09-18 14:35:33 |
合計ジャッジ時間 | 11,524 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sysreadline=sys.stdin.readlineimport heapqimport randomfrom collections import defaultdict,dequeclass Graph:def __init__(self,V,edges=None,graph=None,directed=False,weighted=False,inf=float("inf")):self.V=Vself.directed=directedself.weighted=weightedself.inf=infif graph!=None:self.graph=graphself.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))else:self.edges=edgesself.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)def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False):seen=[False]*self.Vfinished=[False]*self.Vif directed_acyclic or cycle_detection or topological_sort:dag=Trueif euler_tour:et=[]if linked_components:lc=[]if lowlink:order=[None]*self.Vll=[None]*self.Vidx=0if parents or cycle_detection or lowlink or subtree_size:ps=[None]*self.Vif postorder or topological_sort:post=[]if preorder:pre=[]if subtree_size:ss=[1]*self.Vif unweighted_dist or bipartite_graph:uwd=[self.inf]*self.Vuwd[s]=0if weighted_dist:wd=[self.inf]*self.Vwd[s]=0stack=[(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]=Truestack.append((x,d) if self.weighted else x)if euler_tour:et.append(x)if linked_components:lc.append(x)if lowlink:order[x]=idxll[x]=idxidx+=1if preorder:pre.append(x)for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:stack.append((y,d) if self.weighted else y)if parents or cycle_detection or lowlink or subtree_size:ps[y]=xif unweighted_dist or bipartite_graph:uwd[y]=uwd[x]+1if weighted_dist:wd[y]=wd[x]+delif not finished[y]:if (directed_acyclic or cycle_detection or topological_sort) and dag:dag=Falseif cycle_detection:cd=(y,x)elif not finished[x]:finished[x]=Trueif euler_tour:et.append(~x)if lowlink:bl=Truefor y in self.graph[x]:if self.weighted:y,d=yif ps[x]==y and bl:bl=Falsecontinuell[x]=min(ll[x],order[y])if x!=s:ll[ps[x]]=min(ll[ps[x]],ll[x])if postorder or topological_sort:post.append(x)if subtree_size:for y in self.graph[x]:if self.weighted:y,d=yif y==ps[x]:continuess[x]+=ss[y]if bipartite_graph:bg=[[],[]]for tpl in self.edges:x,y=tpl[:2] if self.weighted else tplif uwd[x]==self.inf or uwd[y]==self.inf:continueif not uwd[x]%2^uwd[y]%2:bg=Falsebreakelse:for x in range(self.V):if uwd[x]==self.inf:continuebg[uwd[x]%2].append(x)retu=()if bipartite_graph:retu+=(bg,)if cycle_detection:if dag:cd=[]else:y,x=cdcd=self.Route_Restoration(y,x,ps)retu+=(cd,)if directed_acyclic:retu+=(dag,)if euler_tour:retu+=(et,)if linked_components:retu+=(lc,)if lowlink:retu=(ll,)if parents:retu+=(ps,)if postorder:retu+=(post,)if preorder:retu+=(pre,)if subtree_size:retu+=(ss,)if topological_sort:if dag:tp_sort=post[::-1]else:tp_sort=[]retu+=(tp_sort,)if unweighted_dist:retu+=(uwd,)if weighted_dist:retu+=(wd,)if len(retu)==1:retu=retu[0]return retudef MIV_DFS(self,initial_vertices=None,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False):if initial_vertices==None:initial_vertices=[s for s in range(self.V)]seen=[False]*self.Vfinished=[False]*self.Vif bipartite_graph:bg=[None]*self.Vcnt=-1if directed_acyclic or cycle_detection or topological_sort:dag=Trueif euler_tour:et=[]if linked_components:lc=[]if lowlink:order=[None]*self.Vll=[None]*self.Vidx=0if parents or cycle_detection or lowlink or subtree_size:ps=[None]*self.Vif postorder or topological_sort:post=[]if preorder:pre=[]if subtree_size:ss=[1]*self.Vif bipartite_graph or unweighted_dist:uwd=[self.inf]*self.Vif weighted_dist:wd=[self.inf]*self.Vfor s in initial_vertices:if seen[s]:continueif bipartite_graph:cnt+=1bg[s]=(cnt,0)if linked_components:lc.append([])if bipartite_graph or unweighted_dist:uwd[s]=0if weighted_dist:wd[s]=0stack=[(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]=Truestack.append((x,d) if self.weighted else x)if euler_tour:et.append(x)if linked_components:lc[-1].append(x)if lowlink:order[x]=idxll[x]=idxidx+=1if preorder:pre.append(x)for y in self.graph[x]:if self.weighted:y,d=yif 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 or lowlink or subtree_size:ps[y]=xif unweighted_dist or bipartite_graph:uwd[y]=uwd[x]+1if weighted_dist:wd[y]=wd[x]+delif not finished[y]:if directed_acyclic and dag:dag=Falseif cycle_detection:cd=(y,x)elif not finished[x]:finished[x]=Trueif euler_tour:et.append(~x)if lowlink:bl=Truefor y in self.graph[x]:if self.weighted:y,d=yif ps[x]==y and bl:bl=Falsecontinuell[x]=min(ll[x],order[y])if x!=s:ll[ps[x]]=min(ll[ps[x]],ll[x])if postorder or topological_sort:post.append(x)if subtree_size:for y in self.graph[x]:if self.weighted:y,d=yif y==ps[x]:continuess[x]+=ss[y]if bipartite_graph:bg_=bgbg=[[[],[]] for i in range(cnt+1)]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif not bg_[i][1]^bg_[j][1]:bg[bg_[i][0]]=Falsefor x in range(self.V):if bg[bg_[x][0]]:bg[bg_[x][0]][bg_[x][1]].append(x)retu=()if bipartite_graph:retu+=(bg,)if cycle_detection:if dag:cd=[]else:y,x=cdcd=self.Route_Restoration(y,x,ps)retu+=(cd,)if directed_acyclic:retu+=(dag,)if euler_tour:retu+=(et,)if linked_components:retu+=(lc,)if lowlink:retu=(ll,)if parents:retu+=(ps,)if postorder:retu+=(post,)if preorder:retu+=(pre,)if subtree_size:retu+=(ss,)if topological_sort:if dag:tp_sort=post[::-1]else:tp_sort=[]retu+=(tp_sort,)if unweighted_dist:retu+=(uwd,)if weighted_dist:retu+=(wd,)if len(retu)==1:retu=retu[0]return retudef SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):seen=[False]*self.Vseen[s]=Trueif bfs_tour:bt=[s]if linked_components:lc=[s]if parents:ps=[None]*self.Vif unweighted_dist or bipartite_graph:uwd=[self.inf]*self.Vuwd[s]=0if weighted_dist:wd=[self.inf]*self.Vwd[s]=0queue=deque([s])while queue:x=queue.popleft()for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:seen[y]=Truequeue.append(y)if bfs_tour:bt.append(y)if linked_components:lc.append(y)if parents:ps[y]=xif unweighted_dist or bipartite_graph:uwd[y]=uwd[x]+1if weighted_dist:wd[y]=wd[x]+dif bipartite_graph:bg=[[],[]]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif uwd[i]==self.inf or uwd[j]==self.inf:continueif not uwd[i]%2^uwd[j]%2:bg=Falsebreakelse:for x in range(self.V):if uwd[x]==self.inf:continuebg[uwd[x]%2].append(x)retu=()if bfs_tour:retu+=(bt,)if bipartite_graph:retu+=(bg,)if linked_components:retu+=(lc,)if parents:retu+=(ps,)if unweighted_dist:retu+=(uwd,)if weighted_dist:retu+=(wd,)if len(retu)==1:retu=retu[0]return retudef MIV_BFS(self,initial_vertices=None,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):if initial_vertices==None:initial_vertices=[i for i in range(self.V)]seen=[False]*self.Vif bipartite_graph:bg=[None]*self.Vcnt=-1if linked_components:lc=[]if parents:ps=[None]*self.Vif unweighted_dist:uwd=[self.inf]*self.Vif weighted_dist:wd=[self.inf]*self.Vfor s in initial_vertices:if seen[s]:continueseen[s]=Trueif bipartite_graph:cnt+=1bg[s]=(cnt,0)if linked_components:lc.append([s])if unweighted_dist:uwd[s]=0if weighted_dist:wd[s]=0queue=deque([s])while queue:x=queue.popleft()for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:seen[y]=Truequeue.append(y)if bipartite_graph:bg[y]=(cnt,bg[x][1]^1)if linked_components:lc[-1].append(y)if parents:ps[y]=xif unweighted_dist:uwd[y]=uwd[x]+1if weighted_dist:wd[y]=wd[x]+dif bipartite_graph:bg_=bgbg=[[[],[]] for i in range(cnt+1)]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif not bg_[i][1]^bg_[j][1]:bg[bg_[i][0]]=Falsefor x in range(self.V):if bg[bg_[x][0]]:bg[bg_[x][0]][bg_[x][1]].append(x)retu=()if bipartite_graph:retu+=(bg,)if linked_components:retu+=(lc,)if parents:retu=(ps,)if unweighted_dist:retu+=(uwd,)if weighted_dist:retu+=(wd,)if len(retu)==1:retu=retu[0]return retudef Tree_Diameter(self,weighted=False):def Farthest_Point(u):dist=self.SIV_DFS(u,weighted_dist=True) if weighted else self.SIV_DFS(u,unweighted_dist=True)fp=0for i in range(self.V):if dist[fp]<dist[i]:fp=ireturn fp,dist[fp]u,d=Farthest_Point(0)v,d=Farthest_Point(u)return u,v,ddef SCC(self):reverse_graph=[[] for i in range(self.V)]for tpl in self.edges:u,v=tpl[:2] if self.weighted else tplreverse_graph[v].append(u)postorder=self.MIV_DFS(postorder=True)scc_points=[]seen=[False]*self.Vfor s in postorder[::-1]:if seen[s]:continuequeue=deque([s])seen[s]=Truelst=[]while queue:x=queue.popleft()lst.append(x)for y in reverse_graph[x]:if not seen[y]:seen[y]=Truequeue.append(y)scc_points.append(lst)l=len(scc_points)idx=[None]*self.Vfor i in range(l):for x in scc_points[i]:idx[x]=iscc_edges=set()for tpl in self.edges:u,v=tpl[:2] if self.weighted else tplif idx[u]!=idx[v]:scc_edges.add((idx[u],idx[v]))scc_edges=list(scc_edges)return scc_points,scc_edgesdef Build_LCA(self,s,segment_tree=False):self.lca_segment_tree=segment_treeif self.lca_segment_tree:self.lca_euler_tour,self.lca_parents,depth=self.SIV_DFS(s,euler_tour=True,parents=True,unweighted_dist=True)self.lca_dfs_in_index=[None]*self.Vself.lca_dfs_out_index=[None]*self.Vfor i,x in enumerate(self.lca_euler_tour):if x>=0:self.lca_dfs_in_index[x]=ielse:self.lca_dfs_out_index[~x]=iself.ST=Segment_Tree(2*self.V,lambda x,y:min(x,y),self.V)lst=[None]*(2*self.V)for i in range(2*self.V-1):if self.lca_euler_tour[i]>=0:lst[i]=depth[self.lca_euler_tour[i]]else:lst[i]=depth[self.lca_parents[~self.lca_euler_tour[i]]]lst[2*self.V-1]=-1self.ST.Build(lst)else:self.lca_parents,self.lca_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True)self.lca_parents[s]=sself.lca_PD=Path_Doubling(self.V,self.lca_parents)self.lca_PD.Build_Next(self.V)def LCA(self,a,b):if self.lca_segment_tree:m=min(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b])M=max(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b])x=self.lca_euler_tour[self.ST.Fold_Index(m,M+1)]if x>=0:lca=xelse:lca=self.lca_parents[~x]else:if self.lca_depth[a]>self.lca_depth[b]:a,b=b,ab=self.lca_PD.Permutation_Doubling(b,self.lca_depth[b]-self.lca_depth[a])if a!=b:for k in range(self.lca_PD.k-1,-1,-1):if self.lca_PD.permutation_doubling[a][k]!=self.lca_PD.permutation_doubling[b][k]:a,b=self.lca_PD.permutation_doubling[a][k],self.lca_PD.permutation_doubling[b][k]a,b=self.lca_PD.permutation_doubling[a][0],self.lca_PD.permutation_doubling[b][0]lca=areturn lcadef Build_HLD(self,s):self.hld_parents,size,self.hld_depth=self.SIV_DFS(s,parents=True,subtree_size=True,unweighted_dist=True)stack=[s]self.hld_tour=[]self.hld_path_parents=[None]*self.Vself.hld_path_parents[s]=swhile stack:x=stack.pop()self.hld_tour.append(x)max_size=0max_size_y=Nonefor y in self.graph[x]:if self.weighted:y,d=yif y==self.hld_parents[x]:continueif max_size<size[y]:max_size=size[y]max_size_y=yfor y in self.graph[x]:if self.weighted:y,d=yif y==self.hld_parents[x]:continueif y!=max_size_y:stack.append(y)self.hld_path_parents[y]=yif max_size_y!=None:stack.append(max_size_y)self.hld_path_parents[max_size_y]=self.hld_path_parents[x]self.hld_tour_idx=[None]*self.Vfor i in range(self.V):self.hld_tour_idx[self.hld_tour[i]]=idef HLD(self,a,b,edge=False):L,R=[],[]while self.hld_path_parents[a]!=self.hld_path_parents[b]:if self.hld_depth[self.hld_path_parents[a]]<self.hld_depth[self.hld_path_parents[b]]:R.append((self.hld_tour_idx[self.hld_path_parents[b]],self.hld_tour_idx[b]+1))b=self.hld_parents[self.hld_path_parents[b]]else:L.append((self.hld_tour_idx[a]+1,self.hld_tour_idx[self.hld_path_parents[a]]))a=self.hld_parents[self.hld_path_parents[a]]if edge:if self.hld_depth[a]!=self.hld_depth[b]:retu=L+[(self.hld_tour_idx[a]+1,self.hld_tour_idx[b]+1)]+R[::-1]else:retu=L+R[::-1]else:if self.hld_depth[a]<self.hld_depth[b]:retu=L+[(self.hld_tour_idx[a],self.hld_tour_idx[b]+1)]+R[::-1]else:retu=L+[(self.hld_tour_idx[a]+1,self.hld_tour_idx[b])]+R[::-1]return retudef Build_Hash(self,s,random_number=False,mod=(1<<61)-1,rerooting=False):self.lower_hash=[None]*self.Vif random_number:self.hash_random_number=random_numberelse:self.hash_random_number=[random.randint(1,10**10) for i in range(self.V)]self.hash_mod=modparents,postorder,preorder=self.SIV_DFS(s,parents=True,postorder=True,preorder=True)for x in postorder:level=0for y in self.graph[x]:if self.weighted:y,d=yif y==parents[x]:continueh,l=self.lower_hash[y]level=max(level,l+1)ha=1for y in self.graph[x]:if self.weighted:y,d=yif y==parents[x]:continueh,l=self.lower_hash[y]ha*=h+self.hash_random_number[l]ha%=self.hash_modself.lower_hash[x]=(ha,level)if rerooting:self.upper_hash=[None]*self.Vself.upper_hash[s]=(1,-1)for x in preorder:children=[y for y,d in self.graph[x] if y!=parents[x]] if self.weighted else [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.lower_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.lower_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,0else:ha,level=self.upper_hash[x]h0,l0=l_lst[i]h1,l1=r_lst[i+1]ha*=h0*h1level=max(level,l0+1,l1+1)ha+=self.hash_random_number[level]ha%=self.hash_modlevel+=1self.upper_hash[children[i]]=(ha,level)returndef Hash(self,root,subtree=False):if subtree:ha,level=self.lower_hash[root]ha+=self.hash_random_number[level]ha%=self.hash_modelse:h0,l0=self.lower_hash[root]h1,l1=self.upper_hash[root]ha=(h0*h1+self.hash_random_number[max(l0,l1)])%self.hash_modlevel=max(l0,l1)return ha,leveldef Build_Rerooting(self,s,f,f_merge,subtree=False):self.rerooting_s=sself.rerooting_f=fself.rerooting_f_merge=f_mergeself.subtree=subtreeif self.subtree:parents,postorder,preorder,self.rerooting_depth=self.SIV_DFS(s,parents=True,postorder=True,preorder=True,unweighted_dist=True)parents[s]=sself.rerooting_PD=Path_Doubling(self.V,parents)self.rerooting_PD.Build_Next()parents[s]=Noneelse:parents,postorder,preorder=self.SIV_DFS(s,parents=True,postorder=True,preorder=True)self.rerooting_lower_dp=[None]*self.Vfor x in postorder:children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]]self.rerooting_lower_dp[x]=self.rerooting_f_merge(x,[self.rerooting_f(y,self.rerooting_lower_dp[y]) for y in children])self.rerooting_upper_dp=[None]*self.Vfor x in preorder:children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]]left_accumule_f=[None]*(len(children)+1)right_accumule_f=[None]*(len(children)+1)left_accumule_f[0]=self.rerooting_f_merge(x,[])for i in range(1,len(children)+1):left_accumule_f[i]=self.rerooting_f_merge(x,[left_accumule_f[i-1],self.rerooting_f(children[i-1],self.rerooting_lower_dp[children[i-1]])])right_accumule_f[len(children)]=self.rerooting_f_merge(x,[])for i in range(len(children)-1,-1,-1):right_accumule_f[i]=self.rerooting_f_merge(x,[right_accumule_f[i+1],self.rerooting_f(children[i],self.rerooting_lower_dp[children[i]])])for i in range(len(children)):if parents[x]==None:self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1]]))else:self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1],self.rerooting_upper_dp[x]]))if self.subtree:self.rerooting_parents=parentsdef Rerooting(self,root,subtree=None):assert self.subtree or subtree==Noneif self.subtree and root!=subtree:if self.rerooting_depth[subtree]>=self.rerooting_depth[root]:x=self.rerooting_parents[subtree]else:x=self.rerooting_PD.Permutation_Doubling(root,self.rerooting_depth[root]-self.rerooting_depth[subtree]-1)if self.rerooting_parents[x]!=subtree:x=self.rerooting_parents[subtree]if self.rerooting_parents[subtree]==x:retu=self.rerooting_f(subtree,self.rerooting_lower_dp[subtree])else:retu=self.rerooting_upper_dp[x]else:if root==self.rerooting_s:retu=self.rerooting_f(root,self.rerooting_lower_dp[root])else:retu=self.rerooting_f(root,self.rerooting_f_merge(root,[self.rerooting_lower_dp[root],self.rerooting_upper_dp[root]]))return retudef Build_Approach(self,s):self.approach_parents,self.approach_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True)self.approach_parents[s]=sself.approach_PD=Path_Doubling(self.V,self.approach_parents)self.approach_PD.Build_Next()def Approach(self,x,y):if x==y:return Noneif self.approach_depth[x]>=self.approach_depth[y]:return self.approach_parents[x]retu=self.approach_PD.Permutation_Doubling(y,self.approach_depth[y]-self.approach_depth[x]-1)if self.approach_parents[retu]==x:return retuelse:return self.approach_parents[x]def Centroid(self,root=0):x=rootparents,size=self.SIV_DFS(x,parents=True,subtree_size=True)while True:for y in self.graph[x]:if self.weighted:y,d=yif y==parents[x]:continueif size[y]*2>size[root]:x=ybreakelse:for y in self.graph[x]:if self.weighted:y,d=yif y==parents[x]:continueif size[root]<=2*size[y]:return x,yreturn x,Nonedef Centroid_Decomposition(self,edge=False,linked_point=False,point=False,tree=False):if edge:cd_edges_lst=[None]*self.Vif linked_point:cd_linked_points=[None]*self.Vif point:cd_points_lst=[None]*self.Vif tree:cd_tree=[]*self.Vedges=self.edgespoints=[i for i in range(self.V)]prev_centroid=Nonestack=[(edges,points,None,prev_centroid)] if linked_point else [(edges,points,prev_centroid)]while stack:if linked_point:edges,points,lp,prev_centroid=stack.pop()else:edges,points,prev_centroid=stack.pop()if len(points)==1:centroid=points[0]if edge:cd_edges_lst[centroid]=[]if linked_point:cd_linked_points[centroid]=lpif point:cd_points_lst[centroid]=[centroid]if tree and prev_centroid!=None:cd_tree.append((prev_centroid,centroid))continueG=Graph(len(points),edges=edges,weighted=self.weighted)centroid,_=G.Centroid()if tree and prev_centroid!=None:cd_tree.append((prev_centroid,points[centroid]))parents,tour=G.SIV_DFS(centroid,parents=True,preorder=True)dp=[None]*len(points)edges_lst=[]points_lst=[]if linked_point:linked_points=[]for i,x in enumerate(G.graph[centroid]):if G.weighted:x,d=xdp[x]=(i,0)edges_lst.append([])points_lst.append([points[x]])if linked_point:linked_points.append(points[x])for x in tour[1:]:for y in G.graph[x]:if G.weighted:y,d=yif y==parents[x]:continuei,j=dp[x]jj=len(points_lst[i])edges_lst[i].append((j,jj,d) if G.weighted else (j,jj))points_lst[i].append(points[y])dp[y]=(i,jj)centroid=points[centroid]if edge:cd_edges_lst[centroid]=edgesif linked_point:cd_linked_points[centroid]=lpif point:cd_points_lst[centroid]=pointsif linked_point:for edges,points,lp in zip(edges_lst,points_lst,linked_points):stack.append((edges,points,lp,centroid))else:for edges,points in zip(edges_lst,points_lst):stack.append((edges,points,centroid))retu=()if edge:retu+=(cd_edges_lst,)if linked_point:retu+=(cd_linked_points,)if point:retu+=(cd_points_lst,)if tree:retu+=(cd_tree,)if len(retu)==1:retu=retu[0]return retudef Bridges(self):lowlink,preorder=self.MIV_DFS(lowlink=True,preorder=True)order=[None]*self.Vfor x in range(self.V):order[preorder[x]]=xbridges=[]for e in self.edges:if self.weighted:x,y,d=eelse:x,y=eif order[x]<lowlink[y] or order[y]<lowlink[x]:bridges.append((x,y))return bridgesdef Articulation_Points(self):lowlink,parents,preorder=self.MIV_DFS(lowlink=True,parents=True,preorder=True)order=[None]*self.Vfor x in range(self.V):order[preorder[x]]=xarticulation_points=[]for x in range(self.V):if parents[x]==None:if len({y for y in self.graph[x] if parents[y]==x})>=2:articulation_points.append(x)else:for y in self.graph[x]:if parents[y]!=x:continueif order[x]<=lowlink[y]:articulation_points.append(x)breakreturn articulation_pointsdef TECCD(self):lowlink,preorder=self.MIV_DFS(lowlink=True,preorder=True)order=[None]*self.Vfor x in range(self.V):order[preorder[x]]=xedges=[]for e in self.edges:if self.weighted:x,y,d=eelse:x,y=eif order[x]>=lowlink[y] and order[y]>=lowlink[x]:edges.append((x,y))teccd=Graph(self.V,edges=edges).MIV_DFS(linked_components=True)return teccddef LCD(self):lcd_points=self.MIV_DFS(linked_components=True)lcd_edges=[[] for i in range(len(lcd_points))]idx=[None]*self.Vfor i in range(len(lcd_points)):for j in range(len(lcd_points[i])):idx[lcd_points[i][j]]=(i,j)for tpl in self.edges:if self.weighted:x,y,d=tplelse:x,y=tpli,j0=idx[x]i,j1=idx[y]if self.weighted:lcd_edges[i].append((j0,j1,d))else:lcd_edges[i].append((j0,j1))return lcd_points,lcd_edgesdef Dijkstra(self,s,route_restoration=False):dist=[self.inf]*self.Vdist[s]=0queue=[(0,s)]if route_restoration:parents=[None]*self.Vwhile queue:dx,x=heapq.heappop(queue)if dist[x]<dx:continuefor y,dy in self.graph[x]:if dist[y]>dx+dy:dist[y]=dx+dyif route_restoration:parents[y]=xheapq.heappush(queue,(dist[y],y))if route_restoration:return dist,parentselse:return distdef Bellman_Ford(self,s,route_restoration=False):dist=[self.inf]*self.Vdist[s]=0if route_restoration:parents=[None]*self.Vfor _ in range(self.V-1):for i,j,d in self.edges:if dist[j]>dist[i]+d:dist[j]=dist[i]+dif route_restoration:parents[j]=iif not self.directed and dist[i]>dist[j]+d:dist[i]=dist[j]+dif route_restoration:parents[i]=jnegative_cycle=[]for i,j,d in self.edges:if dist[j]>dist[i]+d:negative_cycle.append(j)if not self.directed and dist[i]>dist[j]+d:negative_cycle.append(i)if negative_cycle:is_negative_cycle=[False]*self.Vfor i in negative_cycle:if is_negative_cycle[i]:continueelse:queue=[i]is_negative_cycle[i]=Truewhile queue:x=queue.popleft()for y,d in self.graph[x]:if not is_negative_cycle[y]:queue.append(y)is_negative_cycle[y]=Trueif route_restoration:parents[y]=xfor i in range(self.V):if is_negative_cycle[i]:dist[i]=-self.infif route_restoration:return dist,parentselse:return distdef Warshall_Floyd(self,route_restoration=False):dist=[[self.inf]*self.V for i in range(self.V)]for i in range(self.V):dist[i][i]=0if route_restoration:parents=[[j for j in range(self.V)] for i in range(self.V)]for i,j,d in self.edges:if i==j:continueif dist[i][j]>d:dist[i][j]=dif route_restoration:parents[i][j]=iif not self.directed and dist[j][i]>d:dist[j][i]=dif route_restoration:parents[j][i]=jfor k in range(self.V):for i in range(self.V):for j in range(self.V):if dist[i][j]>dist[i][k]+dist[k][j]:dist[i][j]=dist[i][k]+dist[k][j]if route_restoration:parents[i][j]=parents[k][j]for i in range(self.V):if dist[i][i]<0:for j in range(self.V):if dist[i][j]!=self.inf:dist[i][j]=-self.infif route_restoration:for i in range(self.V):if dist[i][i]==0:parents[i][i]=Nonereturn dist,parentselse:return distdef BFS_01(self,s,route_restoration=False):queue=deque([s])seen=[False]*self.Vdist=[self.inf]*self.Vdist[s]=0if route_restoration:parents=[None]*self.Vwhile queue:x=queue.popleft()if seen[x]:continueseen[x]=Falsefor y,d in self.graph[x]:if dist[y]>dist[x]+d:dist[y]=dist[x]+dif route_restoration:parents[y]=xif d:queue.append(y)else:queue.appendleft(y)if route_restoration:return dist,parentselse:return distdef Distance_Frequency(self):mod=206158430209cnt=[0]*self.Vcd_edges,cd_points,cd_tree=self.Centroid_Decomposition(edge=True,point=True,tree=True)CD=Graph(self.V,edges=cd_tree)parents,tour=CD.SIV_DFS(cd_tree[0][0],parents=True,postorder=True)for x in tour:C=[0]*(len(cd_points[x])+1)for y in CD.graph[x]:if y==parents[x]:continuedepth=Graph(len(cd_points[y]),edges=cd_edges[y],weighted=self.weighted).SIV_DFS(0,unweighted_dist=True)CC=[0]*(max(depth)+2)for d in depth:CC[d+1]+=1cnt[d+1]+=2C[d+1]+=1poly=NTT_Pow(CC,2)for d,c in enumerate(poly):if d<self.V:cnt[d]-=cwhile C and C[-1]==0:C.pop()poly=NTT_Pow(C,2)for d,c in enumerate(poly):if d<N:cnt[d]+=cfor i in range(self.V):cnt[i]//=2return cntdef Shortest_Path_Count(self,s,dist,mod=0):cnt=[0]*self.Vcnt[s]=1for x in sorted([x for x in range(self.V)],key=lambda x:dist[x]):for y in self.graph[x]:if self.weighted:y,d=yelse:d=1if dist[x]+d==dist[y]:cnt[y]+=cnt[x]if mod:cnt[y]%=modreturn cntdef K_Shortest_Path_Routing(self,s,t,K,edge_unicursal=False,point_unicursal=False):if point_unicursal:if self.weighted:dist,parents=self.Dijkstra(s,route_restoration=True)else:parents,dist=self.SIV_BFS(s,parents=True,unweighted_dist=True)route=tuple(self.Route_Restoration(s,t,parents))queue=[(dist[t],route,[dist[x] for x in route])]set_queue=set()set_queue.add(route)retu=[]while queue and K:d,route,route_dist=heapq.heappop(queue)retu.append((d,route,route_dist))K-=1set_route=set()for i in range(len(route)-1):x=route[i]set_route.add(x)if self.weighted:edges=[(v,u,d) for u,v,d in self.edges if not u in set_route and not v in set_route]else:edges=[(v,u) for u,v in self.edges if not u in set_route and not v in set_route]G_rev=Graph(self.V,edges=edges,directed=self.directed,weighted=self.weighted,inf=self.inf)if self.weighted:dist_rev,parents_rev=G_rev.Dijkstra(t,route_restoration=True)else:parents_rev,dist_rev=G_rev.SIV_BFS(t,parents=True,unweighted_dist=True)for y in self.graph[x]:if self.weighted:y,d=yelse:d=1if y==route[i+1]:continueif dist_rev[y]==self.inf:continuetpl=route[:i+1]+tuple(self.Route_Restoration(t,y,parents_rev)[::-1])if not tpl in set_queue:heapq.heappush(queue,(route_dist[i]+d+dist_rev[y],tpl,route_dist[:i+1]+[route_dist[i]+d+dist_rev[y]-dist_rev[z] for z intpl[i+1:]]))set_queue.add(tpl)elif edge_unicursal:if self.weighted:dist,parents=self.Dijkstra(s,route_restoration=True)else:parents,dist=self.SIV_BFS(s,parents=True,unweighted_dist=True)route=tuple(self.Route_Restoration(s,t,parents))queue=[(dist[t],route,[dist[x] for x in route])]set_queue=set()set_queue.add(route)retu=[]while queue and K:d,route,route_dist=heapq.heappop(queue)retu.append((d,route,route_dist))K-=1set_route=set()for i in range(len(route)-1):x=route[i]y=route[i+1]set_route.add((x,y,route_dist[i+1]-route_dist[i]))if not self.directed:set_route.add((y,x,route_dist[i+1]-route_dist[i]))if self.weighted:edges=[(v,u,d) for u,v,d in self.edges if not (u,v,d) in set_route]else:edges=[(v,u) for u,v in self.edges if not (u,v,d) in set_route]G_rev=Graph(self.V,edges=edges,directed=self.directed,weighted=self.weighted,inf=self.inf)if self.weighted:dist_rev,parents_rev=G_rev.Dijkstra(t,route_restoration=True)else:parents_rev,dist_rev=G_rev.SIV_BFS(t,parents=True,unweighted_dist=True)for y in self.graph[x]:if self.weighted:y,d=yelse:d=1if y==route[i+1]:continueif dist_rev[y]==self.inf:continuetpl=route[:i+1]+tuple(self.Route_Restoration(t,y,parents_rev)[::-1])if not tpl in set_queue:heapq.heappush(queue,(route_dist[i]+d+dist_rev[y],tpl,route_dist[:i+1]+[route_dist[i]+d+dist_rev[y]-dist_rev[z] for z intpl[i+1:]]))set_queue.add(tpl)else:if self.weighted:dist,parents=self.Dijkstra(s,route_restoration=True)else:parents,dist=self.SIV_BFS(s,parents=True,unweighted_dist=True)if dist[t]==self.inf:return Falseroute_lst=[tuple(self.Route_Restoration(s,x,parents)) for x in range(self.V)]if self.weighted:edges_rev=[(j,i,d) for i,j,d in self.edges]else:edges_rev=[(j,i) for i,j in self.edges]G_rev=Graph(self.V,edges=edges_rev,weighted=self.weighted,directed=self.directed,inf=self.inf)if self.weighted:dist_rev,parents_rev=G_rev.Dijkstra(t,route_restoration=True)else:parents_rev,dist_rev=G_rev.SIV_BFS(t,parents=True,unweighted_dist=True)route_rev_lst=[]for x in range(self.V):route_rev_lst.append(tuple(self.Route_Restoration(t,x,parents_rev)[::-1]))route=route_lst[t]queue=[(dist[t],route,[dist[x] for x in route])]set_queue=set()set_queue.add(route)retu=[]while queue and K:d,route,route_dist=heapq.heappop(queue)retu.append((d,route,route_dist))K-=1for i in range(len(route)):x=route[i]for y in self.graph[x]:if self.weighted:y,d=yelse:d=1if i!=len(route)-1 and y==route[i+1]:continuetpl=route[:i+1]+route_rev_lst[y]if not tpl in set_queue:heapq.heappush(queue,(route_dist[i]+d+dist_rev[y],tpl,route_dist[:i+1]+[route_dist[i]+d+dist_rev[y]-dist_rev[z] for z inroute_rev_lst[y]]))set_queue.add(tpl)return retudef Euler_Path(self,s=None,t=None):if self.directed:indegree=[0]*self.Voutdegree=[0]*self.Vgraph=[[] for x in range(self.V)]for tpl in self.edges:if self.weighted:u,v,d=tplelse:u,v=tplindegree[v]+=1outdegree[u]+=1graph[v].append(u)for x in range(self.V):if indegree[x]+1==outdegree[x]:if s==None:s=xelif s!=x:return Falseelif indegree[x]==outdegree[x]+1:if t==None:t=xelif t!=x:return Falseelif indegree[x]!=outdegree[x]:return Falseif (s,t)==(None,None):for x in range(self.V):if graph[x]:s=xt=xbreakelif s==None:s=telif t==None:t=selif s==t:for x in range(self.V):if indegree[x]!=outdegree[x]:return Falsequeue=[t]euler_path=[]while queue:while graph[queue[-1]]:queue.append(graph[queue[-1]].pop())x=queue.pop()euler_path.append(x)for x in range(self.V):if graph[x]:return Falseelse:degree=[0]*self.Vgraph=[[] for x in range(self.V)]use_count=[defaultdict(int) for x in range(self.V)]for tpl in self.edges:if self.weighted:u,v,d=tplelse:u,v=tpldegree[v]+=1degree[u]+=1graph[u].append(v)graph[v].append(u)for x in range(self.V):if degree[x]%2:if s==None and t!=x:s=xelif t==None and s!=x:t=xelif not x in (s,t):return Falseif s==None and t==None:for x in range(self.V):if graph[x]:s=xt=xbreakelse:s,t=0,0elif s==None:s=telif t==None:t=selif s!=t:if degree[s]%2==0 or degree[t]%2==0:return Falsequeue=[t]euler_path=[]while queue:while graph[queue[-1]]:if use_count[queue[-1]][graph[queue[-1]][-1]]:use_count[queue[-1]][graph[queue[-1]][-1]]-=1graph[queue[-1]].pop()else:queue.append(graph[queue[-1]].pop())use_count[queue[-1]][queue[-2]]+=1x=queue.pop()euler_path.append(x)for x in range(self.V):if graph[x]:return Falseif euler_path[0]!=s:return Falsereturn euler_pathdef Route_Restoration(self,s,g,parents):route=[g]while s!=g:if parents[g]==None:route=[]breakg=parents[g]route.append(g)route=route[::-1]return routedef Negative_Cycls(self):dist=[0]*self.Vfor _ in range(self.V-1):for i,j,d in self.edges:dist[j]=min(dist[j],dist[i]+d)for i,j,d in self.edges:if dist[j]>dist[i]+d:return Truereturn Falsedef Kruskal(self,maximize=False):UF=UnionFind(self.V)sorted_edges=sorted(self.edges,key=lambda x:x[2],reverse=maximize)spnning_tree=[]for i,j,d in sorted_edges:if not UF.Same(i,j):UF.Union(i,j)spnning_tree.append((i,j,d))return spnning_treedef Max_Clique(self):graph=[[False]*self.V for x in range(self.V)]for x in range(self.V):for y in self.graph[x]:if self.weighted:y,d=ygraph[x][y]=TrueN0,N1=self.V//2,self.V-self.V//2pop_count=[sum(bit>>i&1 for i in range(N1)) for bit in range(1<<N1)]is_clique0=[True]*(1<<N0)for j in range(N0):for i in range(j):if not graph[i][j]:is_clique0[1<<i|1<<j]=Falsefor i in range(N0):for bit in range(1<<N0):if bit&1<<i:is_clique0[bit]=is_clique0[bit]&is_clique0[bit^1<<i]is_clique1=[True]*(1<<N1)for j in range(N1):for i in range(j):if not graph[i+N0][j+N0]:is_clique1[1<<i|1<<j]=Falsefor i in range(N1):for bit in range(1<<N1):if bit&1<<i:is_clique1[bit]=is_clique1[bit]&is_clique1[bit^1<<i]max_clique_bit=[bit if is_clique0[bit] else 0 for bit in range(1<<N0)]for i in range(N0):for bit in range(1<<N0):if bit&1<<i and pop_count[max_clique_bit[bit]]<pop_count[max_clique_bit[bit^1<<i]]:max_clique_bit[bit]=max_clique_bit[bit^1<<i]dp=[(1<<N0)-1]*(1<<N1)for j in range(N1):for i in range(N0):if not graph[j+N0][i]:dp[1<<j]^=1<<ifor i in range(N1):for bit in range(1<<N1):if bit&1<<i:dp[bit]&=dp[bit^1<<i]bit0,bit1=0,0for bit in range(1<<N1):if is_clique1[bit] and pop_count[max_clique_bit[dp[bit]]]+pop_count[bit]>pop_count[bit0]+pop_count[bit1]:bit0=max_clique_bit[dp[bit]]bit1=bitmax_clique=[i for i in range(N0) if bit0&1<<i]+[i+N0 for i in range(N1) if bit1&1<<i]return max_cliquedef Cliques(self):graph=[[False]*self.V for x in range(self.V)]for x in range(self.V):for y in self.graph[x]:if self.weighted:y,d=ygraph[x][y]=Truecliques=[]points=[x for x in range(self.V)]while points:l=len(points)min_degree,min_degree_point=self.inf,Nonesum_degree=0for x in points:s=sum(graph[x][y] for y in points)sum_degree+=sif s<min_degree:min_degree=smin_degree_point=xif min_degree**2>=sum_degree:lst=pointselse:lst=[x for x in points if x==min_degree_point or graph[min_degree_point][x]]l=len(lst)is_clique=[True]*(1<<l)for j in range(l):for i in range(j):if not graph[lst[i]][lst[j]]:is_clique[1<<i|1<<j]=Falsefor i in range(l):for bit in range(1<<l):if bit&1<<i:is_clique[bit]=is_clique[bit]&is_clique[bit^1<<i]if min_degree**2>=sum_degree:for bit in range(1<<l):if is_clique[bit]:cliques.append([lst[i] for i in range(l) if bit&1<<i])else:idx=lst.index(min_degree_point)for bit in range(1<<l):if is_clique[bit] and bit&1<<idx:cliques.append([lst[i] for i in range(l) if bit&1<<i])if min_degree**2>=sum_degree:points=[]else:points=[x for x in points if x!=min_degree_point]return cliquesdef Coloring_Count(self,mod=0):is_independent_set=[True]*(1<<self.V)for x in range(self.V):for y in self.graph[x]:is_independent_set[1<<x|1<<y]=Falsefor x in range(self.V):for bit in range(1<<self.V):if bit&1<<x:is_independent_set[bit]&=is_independent_set[bit^1<<x]independent_set_count=[int(bl) for bl in is_independent_set]for x in range(self.V):for bit in range(1<<self.V):if bit&1<<x:independent_set_count[bit]+=independent_set_count[bit^1<<x]sign=[None]*(1<<self.V)sign[0]=-1 if self.V%2 else 1for bit in range(1,1<<self.V):sign[bit]=-sign[bit^(bit&-bit)]coloring_count=[0]*(self.V+1)for k in range(self.V+1):for bit in range(1<<self.V):if mod:coloring_count[k]+=pow(independent_set_count[bit],k,mod)*sign[bit]%modcoloring_count[k]%=modelse:coloring_count[k]+=pow(independent_set_count[bit],k)*sign[bit]return coloring_countdef Chromatic_Number(self):coloring_count=self.Coloring_Count(mod=(1<<61)-1)for chromatic_number in range(self.V+1):if coloring_count[chromatic_number]:breakreturn chromatic_numberdef Ford_Fulkerson(self,s,t):max_flow=0residual_graph=[defaultdict(int) for i in range(self.V)]if self.weighted:for i,j,d in self.edges:if not d:continueresidual_graph[i][j]+=dif not self.directed:residual_graph[j][i]+=delse:for i,j in self.edges:residual_graph[i][j]+=1if not self.directed:residual_graph[j][i]+=1while True:parents=[None]*self.Vparents[s]=sseen=[False]*self.Vseen[s]=Truequeue=deque([s])while queue:x=queue.popleft()for y in residual_graph[x].keys():if not seen[y]:seen[y]=Truequeue.append(y)parents[y]=xif y==t:tt=twhile tt!=s:residual_graph[parents[tt]][tt]-=1residual_graph[tt][parents[tt]]+=1if not residual_graph[parents[tt]][tt]:residual_graph[parents[tt]].pop(tt)tt=parents[tt]max_flow+=1breakelse:continuebreakelse:breakreturn max_flowdef BFS(self,s):seen=[False]*self.Vseen[s]=Truequeue=deque([s])while queue:x=queue.popleft()for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:seen[y]=Truequeue.append(y)returndef DFS(self,s):seen=[False]*self.Vfinished=[False]*self.Vstack=[(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]=Truestack.append((x,d) if self.weighted else x)for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:stack.append((y,d) if self.weighted else y)elif not finished[x]:finished[x]=TruereturnN,M,A,B=map(int,readline().split())B+=1edges=[]for a in range(1,A+1):edges.append((0,a))for b in range(B,N+2):edges.append((b,N+2))for m in range(M):L,R=map(int,readline().split())R+=1edges.append((L,R))edges.append((R,L))inf=1<<30G=Graph(N+3,edges=edges,directed=True,inf=inf)ans=G.SIV_BFS(0,unweighted_dist=True)[N+2]if ans==inf:ans=-1else:ans-=2print(ans)