from collections import defaultdict from math import gcd import sys readline=sys.stdin.readline import heapq import random from collections import defaultdict,deque class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if graph: 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)) else: self.edges=edges 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.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 lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.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 lowlink: order[x]=idx ll[x]=idx idx+=1 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 lowlink 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 lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[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=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: x,y=tpl[:2] if self.weighted else tpl if uwd[x]==self.inf or uwd[y]==self.inf: continue if not uwd[x]%2^uwd[y]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=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 retu def 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.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 lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if bipartite_graph or unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([]) if bipartite_graph or unweighted_dist: uwd[s]=0 if weighted_dist: 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[-1].append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 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 or lowlink 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 and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[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=y if y==ps[x]: continue ss[x]+=ss[y] 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) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=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 retu def SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V seen[s]=True if bfs_tour: bt=[s] if linked_components: lc=[s] if parents: ps=[None]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bfs_tour: bt.append(y) if linked_components: lc.append(y) if parents: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if uwd[i]==self.inf or uwd[j]==self.inf: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[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 retu def 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.V if bipartite_graph: bg=[None]*self.V cnt=-1 if linked_components: lc=[] if parents: ps=[None]*self.V if unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue seen[s]=True if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([s]) if unweighted_dist: uwd[s]=0 if weighted_dist: wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if linked_components: lc[-1].append(y) if parents: ps[y]=x if unweighted_dist: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d 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) 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 retu def Tree_Diameter(self,weighted=False): def Farthest_Point(u): dist=self.SIV_BFS(u,weighted_dist=True) if weighted else self.SIV_BFS(u,unweighted_dist=True) fp=0 for i in range(self.V): if dist[fp]=0: self.lca_dfs_in_index[x]=i else: self.lca_dfs_out_index[~x]=i self.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]=-1 self.ST.Build(lst) else: self.lca_parents,self.lca_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True) self.lca_parents[s]=s self.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=x else: lca=self.lca_parents[~x] else: if self.lca_depth[a]>self.lca_depth[b]: a,b=b,a b=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=a return lca def 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.V self.hld_path_parents[s]=s while stack: x=stack.pop() self.hld_tour.append(x) max_size=0 max_size_y=None for y in self.graph[x]: if self.weighted: y,d=y if y==self.hld_parents[x]: continue if max_sizesize[root]: x=y break else: for y in self.graph[x]: if self.weighted: y,d=y if y==parents[x]: continue if size[root]<=2*size[y]: return x,y return x,None def Centroid_Decomposition(self,edge=False,linked_point=False,point=False,tree=False): if edge: cd_edges_lst=[None]*self.V if linked_point: cd_linked_points=[None]*self.V if point: cd_points_lst=[None]*self.V if tree: cd_tree=[]*self.V edges=self.edges points=[i for i in range(self.V)] prev_centroid=None stack=[(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]=lp if point: cd_points_lst[centroid]=[centroid] if tree and prev_centroid!=None: cd_tree.append((prev_centroid,centroid)) continue G=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=x dp[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=y if y==parents[x]: continue i,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]=edges if linked_point: cd_linked_points[centroid]=lp if point: cd_points_lst[centroid]=points if 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 retu def Bridges(self): lowlink,preorder=self.MIV_DFS(lowlink=True,preorder=True) order=[None]*self.V for x in range(self.V): order[preorder[x]]=x bridges=[] for e in self.edges: if self.weighted: x,y,d=e else: x,y=e if order[x]=2: articulation_points.append(x) else: for y in self.graph[x]: if parents[y]!=x: continue if order[x]<=lowlink[y]: articulation_points.append(x) break return articulation_points def TECCD(self): lowlink,preorder=self.MIV_DFS(lowlink=True,preorder=True) order=[None]*self.V for x in range(self.V): order[preorder[x]]=x edges=[] for e in self.edges: if self.weighted: x,y,d=e else: x,y=e if 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 teccd def LCD(self): lcd_points=self.MIV_DFS(linked_components=True) lcd_edges=[[] for i in range(len(lcd_points))] idx=[None]*self.V for 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=tpl else: x,y=tpl i,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_edges def Dijkstra(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 hq=[(0,s)] if route_restoration: parents=[None]*self.V while hq: dx,x=heapq.heappop(hq) if dist[x]dx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(hq,(dist[y],y)) if route_restoration: return dist,parents else: return dist def Bellman_Ford(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 if route_restoration: parents=[None]*self.V for _ in range(self.V-1): for i,j,d in self.edges: if dist[j]>dist[i]+d: dist[j]=dist[i]+d if route_restoration: parents[j]=i if not self.directed and dist[i]>dist[j]+d: dist[i]=dist[j]+d if route_restoration: parents[i]=j negative_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.V for i in negative_cycle: if is_negative_cycle[i]: continue else: queue=[i] is_negative_cycle[i]=True while queue: x=queue.popleft() for y,d in self.graph[x]: if not is_negative_cycle[y]: queue.append(y) is_negative_cycle[y]=True if route_restoration: parents[y]=x for i in range(self.V): if is_negative_cycle[i]: dist[i]=-self.inf if route_restoration: return dist,parents else: return dist def 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]=0 if 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: continue if dist[i][j]>d: dist[i][j]=d if route_restoration: parents[i][j]=i if not self.directed and dist[j][i]>d: dist[j][i]=d if route_restoration: parents[j][i]=j for 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.inf if route_restoration: for i in range(self.V): if dist[i][i]==0: parents[i][i]=None return dist,parents else: return dist def BFS_01(self,s,route_restoration=False): queue=deque([s]) seen=[False]*self.V dist=[self.inf]*self.V dist[s]=0 if route_restoration: parents=[None]*self.V while queue: x=queue.popleft() if seen[x]: continue seen[x]=False for y,d in self.graph[x]: if dist[y]>dist[x]+d: dist[y]=dist[x]+d if route_restoration: parents[y]=x if d: queue.append(y) else: queue.appendleft(y) if route_restoration: return dist,parents else: return dist def Distance_Frequency(self): mod=206158430209 cnt=[0]*self.V cd_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]: continue depth=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]+=1 cnt[d+1]+=2 C[d+1]+=1 poly=NTT_Pow(CC,2) for d,c in enumerate(poly): if ddist[i]+d: return True return False def 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_tree def 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=y graph[x][y]=True N0,N1=self.V//2,self.V-self.V//2 pop_count=[sum(bit>>i&1 for i in range(N1)) for bit in range(1<pop_count[bit0]+pop_count[bit1]: bit0=max_clique_bit[dp[bit]] bit1=bit max_clique=[i for i in range(N0) if bit0&1<=sum_degree: lst=points else: lst=[x for x in points if x==min_degree_point or graph[min_degree_point][x]] l=len(lst) is_clique=[True]*(1<=sum_degree: for bit in range(1<=sum_degree: points=[] else: points=[x for x in points if x!=min_degree_point] return cliques def Ford_Fulkerson(self,s,t): max_flow=0 residual_graph=[defaultdict(int) for i in range(self.V)] if self.weighted: for i,j,d in self.edges: if not d: continue residual_graph[i][j]+=d if not self.directed: residual_graph[j][i]+=d else: for i,j in self.edges: residual_graph[i][j]+=1 if not self.directed: residual_graph[j][i]+=1 while True: parents=[None]*self.V parents[s]=s seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in residual_graph[x].keys(): if not seen[y]: seen[y]=True queue.append(y) parents[y]=x if y==t: tt=t while tt!=s: residual_graph[parents[tt]][tt]-=1 residual_graph[tt][parents[tt]]+=1 if not residual_graph[parents[tt]][tt]: residual_graph[parents[tt]].pop(tt) tt=parents[tt] max_flow+=1 break else: continue break else: break return max_flow def BFS(self,s): seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) return def DFS(self,s): seen=[False]*self.V finished=[False]*self.V 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) 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) elif not finished[x]: finished[x]=True return class UnionFind: def __init__(self,N,label=None,f=None,weighted=False): self.N=N self.parents=[None]*self.N self.size=[1]*self.N self.roots={i for i in range(self.N)} self.label=label if self.label!=None: self.label=[x for x in label] self.f=f self.weighted=weighted if self.weighted: self.weight=[0]*self.N def Find(self,x): stack=[] while self.parents[x]!=None: stack.append(x) x=self.parents[x] if self.weighted: w=0 for y in stack[::-1]: self.parents[y]=x w+=self.weight[y] self.weight[y]=w else: for y in stack[::-1]: self.parents[y]=x return x def Union(self,x,y,w=None): root_x=self.Find(x) root_y=self.Find(y) if root_x==root_y: if self.weighted: if self.weight[y]-self.weight[x]==w: return True else: return False else: if self.size[root_x]