// codesnip-guard: centroid_decomposition
#[cfg_attr(any(),rustfmt::skip)]pub use self::centroid_decomposition::{ContourQueryPointAdd,ContourQueryRange};#[cfg_attr(any(),rustfmt::skip)]mod centroid_decomposition{use super::{AbelianGroup,BinaryIndexedTree,Graph,UndirectedSparseGraph};use std::mem::swap;#[derive(Debug,Clone)]struct RootedTree{parents:Vec<usize>,vs:Vec<usize>}impl RootedTree{fn len(&self)->usize{self.vs.len()}fn split_centroid(self)->CentroidSplit{let n=self.len();assert!(n>2);let parents=&self.parents;let vs=&self.vs;let mut size=vec![1;n];let mut c=usize::MAX;for i in(0..n).rev(){if size[i]>=n.div_ceil(2){c=i;break;}size[parents[i]]+=size[i];}let mut side=vec![u8::MAX;n];let mut order=vec![usize::MAX;n];order[c]=0;let mut count=1usize;let mut taken=0usize;for u in 1..n{if parents[u]==c&&taken+size[u]<=(n-1)/2{taken+=size[u];side[u]=0;order[u]=count;count+=1;}}for u in 1..n{if side[parents[u]]==0{side[u]=0;order[u]=count;count+=1;}}let lsize=count-1;{let mut u=parents[c];while u!=usize::MAX{side[u]=1;order[u]=count;count+=1;u=parents[u];}}for u in 0..n{if u!=c&&side[u]==u8::MAX{side[u]=1;order[u]=count;count+=1;}}assert_eq!(count,n);let mut whole_parents=vec![usize::MAX;n];let mut whole_vs=vec![usize::MAX;n];for u in 0..n{whole_vs[order[u]]=vs[u];}for u in 1..n{let mut x=order[u];let mut y=order[parents[u]];if x>y{swap(&mut x,&mut y);}whole_parents[y]=x;}let left=RootedTree{parents:whole_parents[..=lsize].to_vec(),vs:whole_vs[..=lsize].to_vec()};let right=RootedTree{parents:std::iter::once(usize::MAX).chain(whole_parents[lsize+1..].iter().map(|&p|if p==0{0}else{p-lsize})).collect(),vs:std::iter::once(whole_vs[0]).chain(whole_vs[lsize+1..].iter().copied()).collect()};CentroidSplit{whole:RootedTree{parents:whole_parents,vs:whole_vs},left,right,lsize}}fn centroid_decomposition(self,f:&mut impl FnMut(&[usize],&[usize],usize,usize)){if self.len()<=2{return;}let split=self.split_centroid();f(&split.whole.parents,&split.whole.vs,split.lsize,split.rsize());split.left.centroid_decomposition(f);split.right.centroid_decomposition(f);}}impl From<&UndirectedSparseGraph>for RootedTree{fn from(graph:&UndirectedSparseGraph)->Self{let n=graph.vertices_size();let mut vs=Vec::with_capacity(n);let mut parent=vec![usize::MAX;n];vs.push(0usize);for i in 0..n{let u=vs[i];for a in graph.neighbors(u){if a.to!=parent[u]{vs.push(a.to);parent[a.to]=u;}}}let mut new_idx=vec![0;n];for(i,&v)in vs.iter().enumerate(){new_idx[v]=i;}let mut parents=vec![usize::MAX;n];for v in 1..n{parents[new_idx[v]]=new_idx[parent[v]];}Self{parents,vs}}}#[derive(Debug)]struct CentroidSplit{whole:RootedTree,left:RootedTree,right:RootedTree,lsize:usize}impl CentroidSplit{fn rsize(&self)->usize{self.whole.len()-self.lsize-1}}#[derive(Debug,Clone,Copy)]struct ContourInfo{comp:u32,dep:u32}#[derive(Debug,Clone)]pub struct ContourQueryRange{comp_range:Vec<usize>,info_indptr:Vec<usize>,infos:Vec<ContourInfo>,local_info:Vec<(usize,usize)>,local_offsets:Vec<usize>,local_masks:Vec<u32>}impl ContourQueryRange{pub fn len(&self)->usize{self.comp_range.last().copied().unwrap_or_default()}pub fn is_empty(&self)->bool{self.len()==0}pub fn component_sizes(&self)->impl ExactSizeIterator<Item=usize>+'_{self.comp_range.windows(2).map(|range|range[1]-range[0])}pub fn build_point_add<M:AbelianGroup>(&self,values:&[M::T])->ContourQueryPointAdd<'_,M>{assert_eq!(values.len()+1,self.info_indptr.len());let mut components:Vec<_>=self.component_sizes().map(|n|vec![M::unit();n]).collect();for(v,value)in values.iter().enumerate(){self.for_each_index(v,|c,i|M::operate_assign(&mut components[c][i],value));}ContourQueryPointAdd{geometry:self,values:values.to_vec(),components:components.into_iter().map(|values|{if values.len()<=32{ContourComponent::Values(values)}else{ContourComponent::Bit(BinaryIndexedTree::from_slice(&values))}}).collect()}}#[doc=" Calls `f(component, index)` for each position representing `v`."]pub fn for_each_index(&self,v:usize,mut f:impl FnMut(usize,usize)){for info in&self.infos[self.info_indptr[v]..self.info_indptr[v+1]]{f(info.comp as usize,info.dep as usize);}let(comp,index)=self.local_info[v];if comp!=usize::MAX{f(self.comp_range.len()-1-self.local_offsets.len()+comp,index);}}#[doc=" Calls `f(component, start, end)` for disjoint ranges at distances in `l..r` from `v`."]#[doc=" The ranges exclude `v` itself, even when `l == 0`."]pub fn for_each_contour_range(&self,v:usize,l:usize,r:usize,mut f:impl FnMut(usize,usize,usize)){for info in&self.infos[self.info_indptr[v]..self.info_indptr[v+1]]{let comp=(info.comp^1)as usize;let start=self.comp_range[comp];let len=self.comp_range[comp+1]-start;let lo=l.saturating_sub(info.dep as usize).min(len);let hi=r.saturating_sub(info.dep as usize).min(len);if lo<hi{f(comp,lo,hi);}}let(local,index)=self.local_info[v];if local!=usize::MAX{let comp=self.comp_range.len()-1-self.local_offsets.len()+local;let len=self.comp_range[comp+1]-self.comp_range[comp];let lo=l.max(1).min(len);let hi=r.min(len);if lo<hi{let offset=self.local_offsets[local]+index*(len+1);let mut mask=self.local_masks[offset+hi]^self.local_masks[offset+lo];while mask!=0{let start=mask.trailing_zeros();let end=start+(mask>>start).trailing_ones();f(comp,start as usize,end as usize);mask&=mask.wrapping_add(1<<start);}}}}}enum ContourComponent<M:AbelianGroup>{Values(Vec<M::T>),Bit(BinaryIndexedTree<M>)}pub struct ContourQueryPointAdd<'a,M:AbelianGroup>{geometry:&'a ContourQueryRange,values:Vec<M::T>,components:Vec<ContourComponent<M>>}impl<M:AbelianGroup>ContourQueryPointAdd<'_,M>{pub fn update(&mut self,v:usize,value:M::T){M::operate_assign(&mut self.values[v],&value);self.geometry.for_each_index(v,|c,i|match&mut self.components[c]{ContourComponent::Values(values)=>M::operate_assign(&mut values[i],&value),ContourComponent::Bit(bit)=>bit.update(i,value.clone()),});}pub fn fold(&self,v:usize,l:usize,r:usize)->M::T{let mut result=if l==0&&r!=0{self.values[v].clone()}else{M::unit()};self.geometry.for_each_contour_range(v,l,r,#[inline(always)]|c,start,end|match&self.components[c]{ContourComponent::Values(values)=>{for value in&values[start..end]{M::operate_assign(&mut result,value);}}ContourComponent::Bit(bit)=>{M::operate_assign(&mut result,&bit.fold_abelian(start,end))}});result}}impl UndirectedSparseGraph{#[doc=" 1/3 centroid decomposition"]#[doc=""]#[doc=" - f: (parents: &[usize], vs: &[usize], lsize: usize, rsize: usize)"]#[doc=" - 0: root, 1..=lsize: left subtree, lsize+1..=lsize+rsize: right subtree"]pub fn centroid_decomposition(&self,mut f:impl FnMut(&[usize],&[usize],usize,usize)){if self.vertices_size()<=1{return;}RootedTree::from(self).centroid_decomposition(&mut f);}pub fn contour_query_range(&self)->ContourQueryRange{let n=self.vertices_size();assert!(n<=u32::MAX as usize/2);if n<=1{return ContourQueryRange{comp_range:vec![0],info_indptr:vec![0;n+1],infos:vec![],local_info:vec![(usize::MAX,0);n],local_offsets:vec![],local_masks:vec![]};}let(vertices,start,neighbors)={let(vertices,parents)=self.tree_order(0);let mut indices=vec![0;n];for(i,&v)in vertices.iter().enumerate(){indices[v]=i;}let parents:Vec<_>=vertices.iter().skip(1).map(|&v|indices[parents[v]]as u32).collect();let mut start=vec![0usize;n+1];for(i,&p)in parents.iter().enumerate(){start[i+1]+=1;start[p as usize]+=1;}for i in 1..=n{start[i]+=start[i-1];}let mut neighbors=vec![0u32;2*(n-1)];for(i,&p)in parents.iter().enumerate(){start[i+1]-=1;neighbors[start[i+1]]=p;start[p as usize]-=1;neighbors[start[p as usize]]=i as u32+1;}(vertices,start,neighbors)};let mut comp_range=vec![0usize];let mut vertex_info=Vec::with_capacity(n*(n.ilog2()as usize+1));let mut info_indptr=vec![0usize;n+1];let mut local_info=vec![(usize::MAX,0);n];let mut local_offsets=Vec::new();let mut local_masks=Vec::new();let mut distances=Vec::new();let mut local_sizes=Vec::new();let mut removed=vec![false;n];let mut parents=vec![usize::MAX;n];let mut sizes=vec![0usize;n];let mut tasks=vec![0];let mut order=Vec::with_capacity(n);let mut entries=Vec::with_capacity(n);let mut boundaries=Vec::new();let mut groups=Vec::new();while let Some(root)=tasks.pop(){order.clear();order.push(root);parents[root]=usize::MAX;let mut i=0;while i<order.len(){let v=order[i];sizes[v]=1;for&to in&neighbors[start[v]..start[v+1]]{let to=to as usize;if!removed[to]&&to!=parents[v]{parents[to]=v;order.push(to);}}i+=1;}if order.len()<=32{let len=order.len();if len>1{let comp=local_offsets.len();let offset=local_masks.len();local_offsets.push(offset);local_sizes.push(len);local_masks.resize(offset+len*(len+1),0u32);distances.clear();distances.resize(len*len,0u8);for(i,&v)in order.iter().enumerate(){local_info[vertices[v]]=(comp,i);sizes[v]=i;local_masks[offset+i*(len+1)+1]=1<<i;}for(i,&v)in order.iter().enumerate().skip(1){let parent=sizes[parents[v]];for j in 0..i{let distance=distances[parent*len+j]+1;distances[i*len+j]=distance;distances[j*len+i]=distance;local_masks[offset+i*(len+1)+distance as usize+1]|=1<<j;local_masks[offset+j*(len+1)+distance as usize+1]|=1<<i;}}for row in local_masks[offset..].chunks_exact_mut(len+1){for d in 1..=len{row[d]|=row[d-1];}}}continue;}let mut centroid=root;for&v in order.iter().rev(){if sizes[v]>=order.len().div_ceil(2){centroid=v;break;}sizes[parents[v]]+=sizes[v];}removed[centroid]=true;entries.clear();entries.push((centroid,0));boundaries.clear();boundaries.extend([0,1]);for&v in&neighbors[start[centroid]..start[centroid+1]]{let v=v as usize;if removed[v]{continue;}tasks.push(v);parents[v]=centroid;let mut i=entries.len();entries.push((v,1));while i<entries.len(){let(v,distance)=entries[i];for&to in&neighbors[start[v]..start[v+1]]{let to=to as usize;if!removed[to]&&to!=parents[v]{parents[to]=v;entries.push((to,distance+1));}}i+=1;}boundaries.push(entries.len());}groups.push((0,boundaries.len()-1));while let Some((first,last))=groups.pop(){if last-first<2{continue;}let weight=boundaries[last]-boundaries[first];let target=boundaries[first]+weight.div_ceil(2);let mut middle=first+1+boundaries[first+1..last].partition_point(|&p|p<target);middle=middle.min(last-1);if middle>first+1{let x=boundaries[middle]-boundaries[first];let y=boundaries[middle-1]-boundaries[first];if y.max(weight-y)<x.max(weight-x){middle-=1;}}for(l,r)in[(first,middle),(middle,last)]{let comp=comp_range.len()-1;let mut max_distance=0;for&(v,dep)in&entries[boundaries[l]..boundaries[r]]{vertex_info.push((vertices[v]as u32,ContourInfo{comp:comp as u32,dep:dep as u32}));info_indptr[vertices[v]+1]+=1;max_distance=max_distance.max(dep);}comp_range.push(comp_range[comp]+max_distance+1);}groups.extend([(middle,last),(first,middle)]);}}for len in local_sizes{comp_range.push(comp_range.last().unwrap()+len);}for v in 1..=n{info_indptr[v]+=info_indptr[v-1];}let mut infos=vec![ContourInfo{comp:0,dep:0};vertex_info.len()];let mut positions=info_indptr.clone();for(v,info)in vertex_info{let v=v as usize;infos[positions[v]]=info;positions[v]+=1;}ContourQueryRange{comp_range,info_indptr,infos,local_info,local_offsets,local_masks}}}}
// codesnip-guard: BinaryIndexedTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::binary_indexed_tree::BinaryIndexedTree;#[cfg_attr(any(),rustfmt::skip)]mod binary_indexed_tree{use super::{AbelianGroup,Group,Monoid};use std::fmt::{self,Debug,Formatter};pub struct BinaryIndexedTree<M>where M:Monoid{n:usize,bit:Vec<M::T>}impl<M>Clone for BinaryIndexedTree<M>where M:Monoid{fn clone(&self)->Self{Self{n:self.n,bit:self.bit.clone()}}}impl<M>Debug for BinaryIndexedTree<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("BinaryIndexedTree").field("n",&self.n).field("bit",&self.bit).finish()}}impl<M>BinaryIndexedTree<M>where M:Monoid{#[inline]pub fn new(n:usize)->Self{let bit=vec![M::unit();n+1];Self{n,bit}}#[inline]pub fn from_slice(slice:&[M::T])->Self{let n=slice.len();let mut bit=vec![M::unit();n+1];for(i,x)in slice.iter().enumerate(){let k=i+1;M::operate_assign(&mut bit[k],x);let j=k+(k&(!k+1));if j<=n{bit[j]=M::operate(&bit[j],&bit[k]);}}Self{n,bit}}#[inline]#[doc=" fold [0, k)"]pub fn accumulate0(&self,mut k:usize)->M::T{debug_assert!(k<=self.n);let mut res=M::unit();while k>0{res=M::operate(&self.bit[k],&res);k-=k&(!k+1);}res}#[inline]#[doc=" fold [0, k]"]pub fn accumulate(&self,k:usize)->M::T{self.accumulate0(k+1)}#[inline]pub fn update(&mut self,k:usize,x:M::T){debug_assert!(k<self.n);let mut k=k+1;while k<=self.n{self.bit[k]=M::operate(&self.bit[k],&x);k+=k&(!k+1);}}#[inline]pub fn partition_point_acc<P>(&self,mut pred:P)->usize where P:FnMut(&M::T)->bool{let n=self.n;let mut acc=M::unit();let mut pos=0;let mut k=n.next_power_of_two();while k>0{if k+pos<=n{let nacc=M::operate(&acc,&self.bit[k+pos]);if pred(&nacc){pos+=k;acc=nacc;}}k>>=1;}pos}}impl<G:Group>BinaryIndexedTree<G>{#[inline]pub fn fold(&self,l:usize,r:usize)->G::T{debug_assert!(l<=self.n&&r<=self.n);G::operate(&G::inverse(&self.accumulate0(l)),&self.accumulate0(r))}#[inline]pub fn fold_abelian(&self,mut l:usize,mut r:usize)->G::T where G:AbelianGroup{debug_assert!(l<=self.n&&r<=self.n);if l==r{return G::unit();}let common=l&!(usize::MAX>>(l^r).leading_zeros());let mut left=G::unit();let mut right=G::unit();while l!=common{G::operate_assign(&mut left,&self.bit[l]);l&=l-1;}while r!=common{G::operate_assign(&mut right,&self.bit[r]);r&=r-1;}G::rinv_operate(&right,&left)}#[inline]pub fn get(&self,k:usize)->G::T{self.fold(k,k+1)}#[inline]pub fn set(&mut self,k:usize,x:G::T){self.update(k,G::operate(&G::inverse(&self.get(k)),&x));}}}
// codesnip-guard: Graph
#[cfg_attr(any(),rustfmt::skip)]pub use self::graph_base::*;#[cfg_attr(any(),rustfmt::skip)]mod graph_base{#[doc=" A neighboring vertex and the label of the arc used to reach it."]#[derive(Debug,Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct Neighbor<V,L>{pub to:V,pub label:L}impl<V,L>Neighbor<V,L>{#[inline]pub fn new(to:V,label:L)->Self{Self{to,label}}}impl<V,L>From<(V,L)>for Neighbor<V,L>{#[inline]fn from((to,label):(V,L))->Self{Self::new(to,label)}}#[doc=" A finite graph whose outgoing arcs can be iterated without allocation."]pub trait Graph{type Vertex:Copy+Eq;type Label;type Vertices<'g>:Iterator<Item=Self::Vertex>where Self:'g;type Neighbors<'g>:Iterator<Item=Neighbor<Self::Vertex,Self::Label>>where Self:'g;fn vsize(&self)->usize;fn vertices(&self)->Self::Vertices<'_>;fn neighbors(&self,vertex:Self::Vertex)->Self::Neighbors<'_>;}#[doc=" A graph whose adjacency relation represents directed arcs."]pub trait DirectedGraph:Graph{}pub trait VertexMap<T>:Graph{type Vmap;fn construct_vmap<F>(&self,f:F)->Self::Vmap where F:FnMut()->T;fn vmap_get<'a>(&self,map:&'a Self::Vmap,vertex:Self::Vertex)->&'a T;fn vmap_get_mut<'a>(&self,map:&'a mut Self::Vmap,vertex:Self::Vertex)->&'a mut T;#[inline]fn vmap_set(&self,map:&mut Self::Vmap,vertex:Self::Vertex,value:T){*self.vmap_get_mut(map,vertex)=value;}}pub trait EdgeMap<T>:Graph{type Emap;fn construct_emap<F>(&self,f:F)->Self::Emap where F:FnMut()->T;fn emap_get<'a>(&self,map:&'a Self::Emap,eid:Self::Label)->&'a T;fn emap_get_mut<'a>(&self,map:&'a mut Self::Emap,eid:Self::Label)->&'a mut T;#[inline]fn emap_set(&self,map:&mut Self::Emap,eid:Self::Label,value:T){*self.emap_get_mut(map,eid)=value;}}}
// codesnip-guard: SparseGraph
#[cfg_attr(any(),rustfmt::skip)]pub use self::sparse_graph::*;#[cfg_attr(any(),rustfmt::skip)]mod sparse_graph{use super::{DirectedGraph,EdgeMap,Graph,MarkedScan,Neighbor,Scan,ScanSource,VertexMap};use std::{iter::Copied,marker::PhantomData,ops,slice};type Marker<T>=PhantomData<fn()->T>;#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum DirectedEdge{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum UndirectedEdge{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum BidirectionalEdge{}#[doc=" Static Sparse Graph represented as Compressed Sparse Row."]#[derive(Debug,Clone)]pub struct SparseGraph<D>{vsize:usize,start:Vec<usize>,neighbors:Vec<Neighbor<usize,usize>>,pub edges:Vec<(usize,usize)>,_marker:Marker<D>}impl<D>SparseGraph<D>{#[doc=" Return the number of vertices."]#[inline]pub fn vertices_size(&self)->usize{self.vsize}#[doc=" Return the number of edges."]#[inline]pub fn edges_size(&self)->usize{self.edges.len()}#[doc=" Return an iterator over graph vertices."]#[inline]pub fn vertices(&self)->ops::Range<usize>{0..self.vertices_size()}pub fn builder<T>(vsize:usize)->SparseGraphBuilder<T,D>{SparseGraphBuilder::new(vsize)}pub fn builder_with_esize<T>(vsize:usize,esize:usize)->SparseGraphBuilder<T,D>{SparseGraphBuilder::new_with_esize(vsize,esize)}}pub trait SparseGraphConstruction:Sized{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>;}impl<D>SparseGraph<D>where D:SparseGraphConstruction{#[doc=" Construct graph from edges."]pub fn from_edges(vsize:usize,edges:Vec<(usize,usize)>)->Self{D::construct_graph(vsize,edges)}pub fn reverse_graph(&self)->SparseGraph<D>{let edges=self.edges.iter().map(|&(from,to)|(to,from)).collect();D::construct_graph(self.vsize,edges)}}impl SparseGraphConstruction for DirectedEdge{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>{let mut start:Vec<_>=vec![0usize;vsize+1];for(from,_)in edges.iter().cloned(){start[from]+=1;}for i in 1..=vsize{start[i]+=start[i-1];}let mut neighbors=Vec::<Neighbor<usize,usize>>::with_capacity(edges.len());let ptr=neighbors.as_mut_ptr();for(id,(from,to))in edges.iter().cloned().enumerate(){start[from]-=1;unsafe{ptr.add(start[from]).write(Neighbor::new(to,id))};}unsafe{neighbors.set_len(edges.len())};SparseGraph{vsize,start,neighbors,edges,_marker:PhantomData}}}impl SparseGraphConstruction for UndirectedEdge{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>{let mut start:Vec<_>=vec![0usize;vsize+1];for(from,to)in edges.iter().cloned(){start[to]+=1;start[from]+=1;}for i in 1..=vsize{start[i]+=start[i-1];}let mut neighbors=Vec::<Neighbor<usize,usize>>::with_capacity(edges.len()*2);let ptr=neighbors.as_mut_ptr();for(id,(from,to))in edges.iter().cloned().enumerate(){start[from]-=1;unsafe{ptr.add(start[from]).write(Neighbor::new(to,id))};start[to]-=1;unsafe{ptr.add(start[to]).write(Neighbor::new(from,id))};}unsafe{neighbors.set_len(edges.len()*2)};SparseGraph{vsize,start,neighbors,edges,_marker:PhantomData}}}impl SparseGraphConstruction for BidirectionalEdge{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>{let mut start:Vec<_>=vec![0usize;vsize+1];for(from,to)in edges.iter().cloned(){start[to]+=1;start[from]+=1;}for i in 1..=vsize{start[i]+=start[i-1];}let mut neighbors=Vec::<Neighbor<usize,usize>>::with_capacity(edges.len()*2);let ptr=neighbors.as_mut_ptr();for(id,(from,to))in edges.iter().cloned().enumerate(){start[from]-=1;unsafe{ptr.add(start[from]).write(Neighbor::new(to,id*2))};start[to]-=1;unsafe{ptr.add(start[to]).write(Neighbor::new(from,id*2+1))};}unsafe{neighbors.set_len(edges.len()*2)};SparseGraph{vsize,start,neighbors,edges,_marker:PhantomData}}}pub type DirectedSparseGraph=SparseGraph<DirectedEdge>;pub type UndirectedSparseGraph=SparseGraph<UndirectedEdge>;pub type BidirectionalSparseGraph=SparseGraph<BidirectionalEdge>;pub struct SparseGraphBuilder<T,D>{vsize:usize,edges:Vec<(usize,usize)>,rest:Vec<T>,_marker:Marker<D>}impl<T,D>SparseGraphBuilder<T,D>{pub fn new(vsize:usize)->Self{Self{vsize,edges:Default::default(),rest:Default::default(),_marker:PhantomData}}pub fn new_with_esize(vsize:usize,esize:usize)->Self{Self{vsize,edges:Vec::with_capacity(esize),rest:Vec::with_capacity(esize),_marker:PhantomData}}pub fn add_edge(&mut self,u:usize,v:usize,w:T){self.edges.push((u,v));self.rest.push(w);}}impl<T,D>SparseGraphBuilder<T,D>where D:SparseGraphConstruction{pub fn build(self)->(SparseGraph<D>,Vec<T>){let graph=SparseGraph::from_edges(self.vsize,self.edges);(graph,self.rest)}}pub struct SparseGraphScanner<U,T,D>where U:Scan<Output=usize>,T:Scan{vsize:usize,esize:usize,_marker:Marker<(U,T,D)>}impl<U,T,D>SparseGraphScanner<U,T,D>where U:Scan<Output=usize>,T:Scan{pub fn new(vsize:usize,esize:usize)->Self{Self{vsize,esize,_marker:PhantomData}}}impl<U,T,D>MarkedScan for SparseGraphScanner<U,T,D>where U:Scan<Output=usize>,T:Scan,D:SparseGraphConstruction{type Output=(SparseGraph<D>,Vec<<T as Scan>::Output>);fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut builder=SparseGraphBuilder::new_with_esize(self.vsize,self.esize);for _ in 0..self.esize{builder.add_edge(U::scan(iter)?,U::scan(iter)?,T::scan(iter)?);}Some(builder.build())}}pub type DirectedGraphScanner<U,T=()>=SparseGraphScanner<U,T,DirectedEdge>;pub type UndirectedGraphScanner<U,T=()>=SparseGraphScanner<U,T,UndirectedEdge>;pub type BidirectionalGraphScanner<U,T=()>=SparseGraphScanner<U,T,BidirectionalEdge>;pub struct TreeGraphScanner<U,T=()>where U:Scan<Output=usize>,T:Scan{vsize:usize,_marker:Marker<(U,T)>}impl<U,T>TreeGraphScanner<U,T>where U:Scan<Output=usize>,T:Scan{pub fn new(vsize:usize)->Self{Self{vsize,_marker:PhantomData}}}impl<U,T>MarkedScan for TreeGraphScanner<U,T>where U:Scan<Output=usize>,T:Scan{type Output=(UndirectedSparseGraph,Vec<<T as Scan>::Output>);fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{UndirectedGraphScanner::<U,T>::new(self.vsize,self.vsize-1).mscan(iter)}}impl<D>Graph for SparseGraph<D>where D:SparseGraphConstruction{type Vertex=usize;type Label=usize;type Vertices<'g>=ops::Range<usize>where D:'g;type Neighbors<'g>=Copied<slice::Iter<'g,Neighbor<usize,usize>>>where D:'g;#[inline]fn vsize(&self)->usize{self.vsize}#[inline]fn vertices(&self)->Self::Vertices<'_>{0..self.vsize}#[inline]fn neighbors(&self,vertex:Self::Vertex)->Self::Neighbors<'_>{self.neighbors[self.start[vertex]..self.start[vertex+1]].iter().copied()}}impl DirectedGraph for SparseGraph<DirectedEdge>{}impl<T>EdgeMap<T>for SparseGraph<DirectedEdge>{type Emap=Vec<T>;#[inline]fn construct_emap<F>(&self,f:F)->Self::Emap where F:FnMut()->T{let mut map=Vec::with_capacity(self.edges.len());map.resize_with(self.edges.len(),f);map}#[inline]fn emap_get<'a>(&self,map:&'a Self::Emap,eid:Self::Label)->&'a T{&map[eid]}#[inline]fn emap_get_mut<'a>(&self,map:&'a mut Self::Emap,eid:Self::Label)->&'a mut T{&mut map[eid]}}impl<T>EdgeMap<T>for SparseGraph<UndirectedEdge>{type Emap=Vec<T>;#[inline]fn construct_emap<F>(&self,f:F)->Self::Emap where F:FnMut()->T{let mut map=Vec::with_capacity(self.edges.len());map.resize_with(self.edges.len(),f);map}#[inline]fn emap_get<'a>(&self,map:&'a Self::Emap,eid:Self::Label)->&'a T{&map[eid]}#[inline]fn emap_get_mut<'a>(&self,map:&'a mut Self::Emap,eid:Self::Label)->&'a mut T{&mut map[eid]}}impl<D,T>VertexMap<T>for SparseGraph<D>where D:SparseGraphConstruction{type Vmap=Vec<T>;#[inline]fn construct_vmap<F>(&self,f:F)->Self::Vmap where F:FnMut()->T{let mut v=Vec::with_capacity(self.vsize);v.resize_with(self.vsize,f);v}#[inline]fn vmap_get<'a>(&self,map:&'a Self::Vmap,vid:Self::Vertex)->&'a T{&map[vid]}#[inline]fn vmap_get_mut<'a>(&self,map:&'a mut Self::Vmap,vid:Self::Vertex)->&'a mut T{&mut map[vid]}}}
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}
// codesnip-guard: array
#[cfg_attr(any(),rustfmt::skip)]mod array{#[macro_export]macro_rules!array{[@inner$data:ident=[$init:expr;$len:expr]]=>{{use::std::mem::{ManuallyDrop,MaybeUninit};let mut$data:[MaybeUninit<_>;$len]=unsafe{MaybeUninit::uninit().assume_init()};$init;#[repr(C)]union __Transmuter<const N:usize,T:Clone>{src:ManuallyDrop<[MaybeUninit<T>;N]>,dst:ManuallyDrop<[T;N]>,}ManuallyDrop::into_inner(unsafe{__Transmuter{src:ManuallyDrop::new($data)}.dst})}};[||$e:expr;$len:expr]=>{$crate::array![@inner data=[data.iter_mut().for_each(|item|*item=MaybeUninit::new($e));$len]]};[|$i:pat_param|$e:expr;$len:expr]=>{$crate::array![@inner data=[data.iter_mut().enumerate().for_each(|($i,item)|*item=MaybeUninit::new($e));$len]]};[$e:expr;$len:expr]=>{{let e=$e;$crate::array![||Clone::clone(&e);$len]}};}}
// codesnip-guard: scanner
#[cfg_attr(any(),rustfmt::skip)]pub use self::scanner::*;#[cfg_attr(any(),rustfmt::skip)]mod scanner{use std::{iter::{FromIterator,from_fn,repeat_with},marker::PhantomData};pub fn read_stdin_all()->String{use std::io::Read as _;let mut s=String::new();std::io::stdin().read_to_string(&mut s).expect("io error");s}pub fn read_stdin_all_unchecked()->String{use std::io::Read as _;let mut buf=Vec::new();std::io::stdin().read_to_end(&mut buf).expect("io error");unsafe{String::from_utf8_unchecked(buf)}}pub fn read_all(mut reader:impl std::io::Read)->String{let mut s=String::new();reader.read_to_string(&mut s).expect("io error");s}pub fn read_all_unchecked(mut reader:impl std::io::Read)->String{let mut buf=Vec::new();reader.read_to_end(&mut buf).expect("io error");unsafe{String::from_utf8_unchecked(buf)}}pub fn read_stdin_line()->String{let mut s=String::new();std::io::stdin().read_line(&mut s).expect("io error");s}pub trait Scan:Sized{type Output;fn scan<S:ScanSource>(source:&mut S)->Option<Self::Output>;fn scan_vec<S:ScanSource>(source:&mut S,size:usize,capacity:usize)->Vec<Self::Output>{let mut values=Vec::with_capacity(capacity.max(size));values.extend((0..size).map(|_|source.scan::<Self>()));values}}pub trait MarkedScan:Sized{type Output;fn mscan<S:ScanSource>(self,source:&mut S)->Option<Self::Output>;}pub trait ScanSource:Sized{#[doc=" Reads a token under the source's input requirements."]#[doc=" Checked sources return `None` at EOF; unchecked sources require available input."]fn next_token(&mut self)->Option<&str>;#[doc=" Skips separators without consuming the next token."]#[inline]fn skip_whitespace(&mut self){}#[inline]fn read_u8(&mut self)->Option<u8>{self.next_token()?.parse().ok()}#[inline]fn read_u16(&mut self)->Option<u16>{self.next_token()?.parse().ok()}#[inline]fn read_u32(&mut self)->Option<u32>{self.next_token()?.parse().ok()}fn read_u32_vec(&mut self,size:usize,capacity:usize)->Vec<u32>{let mut values=Vec::with_capacity(capacity.max(size));values.extend((0..size).map(|_|self.scan::<u32>()));values}#[inline]fn read_u64(&mut self)->Option<u64>{self.next_token()?.parse().ok()}#[inline]fn read_u128(&mut self)->Option<u128>{self.next_token()?.parse().ok()}#[inline]fn read_usize(&mut self)->Option<usize>{self.next_token()?.parse().ok()}#[inline]fn read_i8(&mut self)->Option<i8>{self.next_token()?.parse().ok()}#[inline]fn read_i16(&mut self)->Option<i16>{self.next_token()?.parse().ok()}#[inline]fn read_i32(&mut self)->Option<i32>{self.next_token()?.parse().ok()}#[inline]fn read_i64(&mut self)->Option<i64>{self.next_token()?.parse().ok()}#[inline]fn read_i128(&mut self)->Option<i128>{self.next_token()?.parse().ok()}#[inline]fn read_isize(&mut self)->Option<isize>{self.next_token()?.parse().ok()}#[doc=" Panics if reading fails."]#[inline]fn scan<T:Scan>(&mut self)->T::Output{T::scan(self).expect("scan error")}#[doc=" Panics if reading fails."]#[inline]fn mscan<T:MarkedScan>(&mut self,marker:T)->T::Output{marker.mscan(self).expect("scan error")}fn scan_vec<T:Scan>(&mut self,size:usize,capacity:usize)->Vec<T::Output>{if size==0{self.skip_whitespace();}T::scan_vec(self,size,capacity)}#[inline]fn iter<T:Scan>(&mut self)->ScannerIter<'_,Self,T>{ScannerIter{inner:self,_marker:PhantomData}}}#[derive(Clone,Debug)]pub struct Scanner<'a,I:Iterator<Item=&'a str>=std::str::SplitAsciiWhitespace<'a>>{iter:I}impl<'a>Scanner<'a>{pub fn new(s:&'a str)->Self{Self{iter:s.split_ascii_whitespace()}}}impl<'a,I:Iterator<Item=&'a str>>Scanner<'a,I>{pub fn new_from_iter(iter:I)->Self{Self{iter}}}impl<'a,I:Iterator<Item=&'a str>>ScanSource for Scanner<'a,I>{fn next_token(&mut self)->Option<&str>{self.iter.next()}}macro_rules!impl_scan{($($t:ty)*)=>{$(impl Scan for$t{type Output=Self;fn scan<I:ScanSource>(iter:&mut I)->Option<Self>{iter.next_token()?.parse::<$t>().ok()}})*};}impl_scan!(char f32 f64 String);macro_rules!impl_integer_scan{($($t:ty=>$read:ident),*$(,)?)=>{$(impl Scan for$t{type Output=Self;#[inline]fn scan<S:ScanSource>(source:&mut S)->Option<Self>{source.$read()}})*};}impl_integer_scan!(u8=>read_u8,u16=>read_u16,u64=>read_u64,u128=>read_u128,usize=>read_usize,i8=>read_i8,i16=>read_i16,i32=>read_i32,i64=>read_i64,i128=>read_i128,isize=>read_isize,);impl Scan for u32{type Output=Self;#[inline]fn scan<S:ScanSource>(source:&mut S)->Option<Self>{source.read_u32()}fn scan_vec<S:ScanSource>(source:&mut S,size:usize,capacity:usize)->Vec<Self>{source.read_u32_vec(size,capacity)}}macro_rules!impl_scan_tuple{(@impl$($T:ident)*)=>{impl<$($T:Scan),*>Scan for($($T,)*){type Output=($(<$T as Scan>::Output,)*);fn scan<It:ScanSource>(_iter:&mut It)->Option<Self::Output>{Some(($(<$T as Scan>::scan(_iter)?,)*))}}};(@inner$($T:ident)*,)=>{impl_scan_tuple!(@impl$($T)*);};(@inner$($T:ident)*,$U:ident$($Rest:ident)*)=>{impl_scan_tuple!(@impl$($T)*);impl_scan_tuple!(@inner$($T)*$U,$($Rest)*);};($($T:ident)*)=>{impl_scan_tuple!(@inner,$($T)*);};}impl_scan_tuple!(A B C D E F G H I J K);pub struct ScannerIter<'a,S,T>{inner:&'a mut S,_marker:PhantomData<fn()->T>}impl<S:ScanSource,T:Scan>Iterator for ScannerIter<'_,S,T>{type Item=T::Output;#[inline]fn next(&mut self)->Option<Self::Item>{T::scan(self.inner)}}#[doc=" scan a value with Scanner"]#[doc=""]#[doc=" - `scan_value!(scanner, ELEMENT)`"]#[doc=""]#[doc=" ELEMENT :="]#[doc=" - `$ty`: Scan"]#[doc=" - `&str`: borrowed token; the source stays borrowed until its last use"]#[doc=" - `@$expr`: MarkedScan"]#[doc=" - `$ty = $expr`: MarkedScan"]#[doc=" - `[ELEMENT; $expr]`: vector"]#[doc=" - `[$ty; $len; capacity $capacity]`: vector with reserved capacity"]#[doc=" - `[ELEMENT; const $expr]`: array"]#[doc=" - `[ELEMENT]`: iterator"]#[doc=" - `[ELEMENT; iter $expr]`: iterator of the specified length"]#[doc=" - `($(ELEMENT)*,)`: tuple"]#[macro_export]macro_rules!scan_value{(@repeat$scanner:expr,[$($t:tt)*]$len:expr)=>{{$crate::scan_value!(@iter$scanner,[$($t)*]$len).collect::<Vec<_>>()}};(@repeat$scanner:expr,[$($t:tt)*])=>{{::std::iter::repeat_with(||$crate::scan_value!(@inner$scanner,[]$($t)*))}};(@iter$scanner:expr,[$($t:tt)*]$len:expr)=>{{let size=$len;if size==0{$scanner.skip_whitespace();}$crate::scan_value!(@repeat$scanner,[$($t)*]).take(size)}};(@array$scanner:expr,[$($t:tt)*]$len:expr)=>{{if$len==0{$scanner.skip_whitespace();}$crate::array![||$crate::scan_value!(@inner$scanner,[]$($t)*);$len]}};(@tuple$scanner:expr,[$([$($args:tt)*])*])=>{($($($args)*,)*)};(@sparen$scanner:expr,[]@$e:expr;$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[@$e]$($t)*)};(@sparen$scanner:expr,[]($($tt:tt)*);$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[($($tt)*)]$($t)*)};(@sparen$scanner:expr,[][$($tt:tt)*];$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[[$($tt)*]]$($t)*)};(@sparen$scanner:expr,[]$ty:ty=$e:expr;$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[$ty=$e]$($t)*)};(@sparen$scanner:expr,[]$ty:ty;$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[$ty]$($t)*)};(@sparen$scanner:expr,[]$($args:tt)*)=>{$crate::scan_value!(@repeat$scanner,[$($args)*])};(@sparen$scanner:expr,[$($args:tt)+]const$len:expr)=>{$crate::scan_value!(@array$scanner,[$($args)+]$len)};(@sparen$scanner:expr,[$($args:tt)+]iter$len:expr)=>{$crate::scan_value!(@iter$scanner,[$($args)+]$len)};(@sparen$scanner:expr,[$($args:tt)+]$len:expr;capacity$capacity:expr)=>{{let size=$len;let capacity=$capacity;$scanner.scan_vec::<$($args)+>(size,capacity)}};(@sparen$scanner:expr,[$($args:tt)+]$len:expr)=>{$crate::scan_value!(@repeat$scanner,[$($args)+]$len)};(@$tag:ident$scanner:expr,[[$($args:tt)*]])=>{$($args)*};(@$tag:ident$scanner:expr,[$($args:tt)*]@$e:expr$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$scanner.mscan($e)]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*]($($tuple:tt)*)$($t:tt)*)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$crate::scan_value!(@tuple$scanner,[]$($tuple)*)]]$($t)*)};(@$tag:ident$scanner:expr,[$($args:tt)*][$($tt:tt)*]$($t:tt)*)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$crate::scan_value!(@sparen$scanner,[]$($tt)*)]]$($t)*)};(@$tag:ident$scanner:expr,[$($args:tt)*]&str$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$scanner.next_token().expect("scan error")]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*]$ty:ty=$e:expr$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[{let _tmp:$ty=$scanner.mscan($e);_tmp}]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*]$ty:ty$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$scanner.scan::<$ty>()]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*],$($t:tt)*)=>{$crate::scan_value!(@$tag$scanner,[$($args)*]$($t)*)};(@$tag:ident$scanner:expr,[$($args:tt)*])=>{::std::compile_error!(::std::stringify!($($args)*))};(src=$src:expr,$($t:tt)*)=>{{let mut __scanner=Scanner::new($src);$crate::scan_value!(@inner __scanner,[]$($t)*)}};(iter=$iter:expr,$($t:tt)*)=>{{let mut __scanner=Scanner::new_from_iter($iter);$crate::scan_value!(@inner __scanner,[]$($t)*)}};($scanner:expr,$($t:tt)*)=>{$crate::scan_value!(@inner$scanner,[]$($t)*)}}#[doc=" scan and bind values with Scanner"]#[doc=""]#[doc=" - `scan!(scanner, $($pat $(: ELEMENT)?),*)`"]#[macro_export]macro_rules!scan{(@assert$p:pat)=>{};(@assert$($p:tt)*)=>{::std::compile_error!(::std::concat!("expected pattern, found `",::std::stringify!($($p)*),"`"));};(@pat$scanner:expr,[][])=>{};(@pat$scanner:expr,[][],$($t:tt)*)=>{$crate::scan!(@pat$scanner,[][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]$x:ident$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*$x][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]::$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*::][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]&$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*&][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]($($x:tt)*)$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*($($x)*)][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][][$($x:tt)*]$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*[$($x)*]][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]{$($x:tt)*}$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*{$($x)*}][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]:$($t:tt)*)=>{$crate::scan!(@ty$scanner,[$($p)*][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]$($t:tt)*)=>{$crate::scan!(@let$scanner,[$($p)*][usize]$($t)*)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]@$e:expr$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*@$e]$(,$($t)*)?)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]($($x:tt)*)$($t:tt)*)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*($($x)*)]$($t)*)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*][$($x:tt)*]$($t:tt)*)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*[$($x)*]]$($t)*)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]&str$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*&str]$(,$($t)*)?)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]$ty:ty=$e:expr$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*$ty=$e]$(,$($t)*)?)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]$ty:ty$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*$ty]$(,$($t)*)?)};(@let$scanner:expr,[$($p:tt)*][$($tt:tt)*]$($t:tt)*)=>{$crate::scan!{@assert$($p)*}let$($p)* =$crate::scan_value!($scanner,$($tt)*);$crate::scan!(@pat$scanner,[][]$($t)*)};(src=$src:expr,$($t:tt)*)=>{let mut __scanner=Scanner::new($src);$crate::scan!(@pat __scanner,[][]$($t)*)};(iter=$iter:expr,$($t:tt)*)=>{let mut __scanner=Scanner::new_from_iter($iter);$crate::scan!(@pat __scanner,[][]$($t)*)};($scanner:expr,$($t:tt)*)=>{$crate::scan!(@pat$scanner,[][]$($t)*)}}#[doc=" define enum scan rules"]#[doc=""]#[doc=" # Example"]#[doc=" ```rust"]#[doc=" # use competitive::{define_enum_scan, tools::{CharsWithBase, Scan, ScanSource, Scanner, Usize1}};"]#[doc=" define_enum_scan! {"]#[doc="   enum Query: u8 {"]#[doc="     0 => Noop,"]#[doc="     1 => Args { i: Usize1, s: char },"]#[doc="     9 => Complex { n: usize, c: [(usize, Vec<usize> = CharsWithBase('a')); n] },"]#[doc="   }"]#[doc=" }"]#[doc=" ```"]#[macro_export]macro_rules!define_enum_scan{(@field_ty@repeat[$($t:tt)*]$($len:expr)?)=>{Vec<$crate::define_enum_scan!(@field_ty$($t)*)>};(@field_ty@array[$($t:tt)*]$len:expr)=>{[$crate::define_enum_scan!(@field_ty$($t)*);$len]};(@field_ty@tuple[$([$($args:tt)*])*])=>{($($($args)*,)*)};(@field_ty@sparen[]($($tt:tt)*);$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[($($tt)*)]$($t)*)};(@field_ty@sparen[][$($tt:tt)*];$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[[$($tt)*]]$($t)*)};(@field_ty@sparen[]$ty:ty=$e:expr;$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[$ty=$e]$($t)*)};(@field_ty@sparen[]$ty:ty;$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[$ty]$($t)*)};(@field_ty@sparen[]$($args:tt)*)=>{$crate::define_enum_scan!(@field_ty@repeat[$($args)*])};(@field_ty@sparen[$($args:tt)+]const$len:expr)=>{$crate::define_enum_scan!(@field_ty@array[$($args)+]$len)};(@field_ty@sparen[$($args:tt)+]$len:expr)=>{$crate::define_enum_scan!(@field_ty@repeat[$($args)+]$len)};(@field_ty@$tag:ident[$($args:tt)*]($($tuple:tt)*)$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[$crate::define_enum_scan!(@field_ty@tuple[]$($tuple)*)]]$($t)*)};(@field_ty@$tag:ident[$($args:tt)*][$($tt:tt)*]$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[$crate::define_enum_scan!(@field_ty@sparen[]$($tt)*)]]$($t)*)};(@field_ty@$tag:ident[$($args:tt)*]$ty:ty=$e:expr$(,$($t:tt)*)?)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[$ty]]$(,$($t)*)?)};(@field_ty@$tag:ident[$($args:tt)*]$ty:ty$(,$($t:tt)*)?)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[<$ty as Scan>::Output]]$(,$($t)*)?)};(@field_ty@$tag:ident[$($args:tt)*],$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*]$($t)*)};(@field_ty@$tag:ident[[$($args:tt)*]])=>{$($args)*};(@field_ty@$tag:ident[$($args:tt)*])=>{::std::compile_error!(::std::stringify!($($args)*))};(@field_ty$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@inner[]$($t)*)};(@tag_expr raw,$iter:ident)=>{ScanSource::next_token($iter)?};(@tag_expr$d:ty,$iter:ident)=>{<$d as Scan>::scan($iter)?};(@variant([$($attr:tt)*]$vis:vis$T:ident$d:tt)[$($vars:tt)*])=>{$crate::define_enum_scan!{@def$($attr)*$vis enum$T:$d{$($vars)*}}};(@variant$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident{$($fs:tt)*}$($rest:tt)*)=>{$crate::define_enum_scan!{@field$ctx[$($vars)*]$p=>$v[]$($fs)*;$($rest)*}};(@variant$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*$p=>$v,]$($rest)*}};(@variant$ctx:tt[$($vars:tt)*],$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*]$($rest)*}};(@endfield$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*][$f:ident:$($spec:tt)*],$($rest:tt)*)=>{$crate::define_enum_scan!{@field$ctx[$($vars)*]$p=>$v[$($fs)*[$f:$($spec)*]]$($rest)*}};(@endfield$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*][$f:ident:$($spec:tt)*];$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*$p=>$v{$($fs)*[$f:$($spec)*]},]$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*];$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*$p=>$v{$($fs)*},]$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:($($tuple:tt)*)$sep:tt$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:($($tuple)*)]$sep$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:[$($x:tt)*]$sep:tt$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:[$($x)*]]$sep$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty=$e:expr,$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty=$e],$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty;$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty];$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty=$e:expr;$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty=$e];$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty,$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty],$($rest)*}};(@def$(#[$attr:meta])*$vis:vis enum$T:ident:$d:tt{$($p:pat=>$v:ident$({$([$f:ident:$($spec:tt)*])*})?,)*})=>{$(#[$attr])*$vis enum$T{$($v$({$($f:$crate::define_enum_scan!(@field_ty$($spec)*)),*})?),*}impl Scan for$T{type Output=Self;fn scan<I:ScanSource>(iter:&mut I)->Option<Self>{let tag=$crate::define_enum_scan!(@tag_expr$d,iter);match tag{$($p=>{$($(let$f=$crate::scan_value!((*iter),$($spec)*);)*)?Some($T::$v$({$($f),*})?)}),*_=>None,}}}};($(#[$attr:meta])*$vis:vis enum$T:ident:raw{$($body:tt)*})=>{$crate::define_enum_scan!{@variant([$(#[$attr])*]$vis$T raw)[]$($body)*}};($(#[$attr:meta])*$vis:vis enum$T:ident:$d:ty{$($body:tt)*})=>{$crate::define_enum_scan!{@variant([$(#[$attr])*]$vis$T$d)[]$($body)*}};}#[derive(Debug,Copy,Clone)]pub enum Usize1{}impl Scan for Usize1{type Output=usize;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{<usize as Scan>::scan(iter)?.checked_sub(1)}}#[derive(Debug,Copy,Clone)]pub struct CharWithBase(pub char);impl MarkedScan for CharWithBase{type Output=usize;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some((<char as Scan>::scan(iter)?as u8-self.0 as u8)as usize)}}#[derive(Debug,Copy,Clone)]pub enum Chars{}impl Scan for Chars{type Output=Vec<char>;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.chars().collect())}}#[derive(Debug,Copy,Clone)]pub struct CharsWithBase(pub char);impl MarkedScan for CharsWithBase{type Output=Vec<usize>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.chars().map(|c|(c as u8-self.0 as u8)as usize).collect())}}#[derive(Debug,Copy,Clone)]pub enum Byte1{}impl Scan for Byte1{type Output=u8;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{let bytes=iter.next_token()?.as_bytes();assert_eq!(bytes.len(),1);Some(bytes[0])}}#[derive(Debug,Copy,Clone)]pub struct ByteWithBase(pub u8);impl MarkedScan for ByteWithBase{type Output=usize;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some((<char as Scan>::scan(iter)?as u8-self.0)as usize)}}#[derive(Debug,Copy,Clone)]pub enum Bytes{}impl Scan for Bytes{type Output=Vec<u8>;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.bytes().collect())}}#[derive(Debug,Copy,Clone)]pub struct BytesWithBase(pub u8);impl MarkedScan for BytesWithBase{type Output=Vec<usize>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.bytes().map(|c|(c-self.0)as usize).collect())}}#[derive(Debug,Copy,Clone)]pub struct Collect<T,B=Vec<<T as Scan>::Output>>where T:Scan,B:FromIterator<<T as Scan>::Output>{size:usize,_marker:PhantomData<fn()->(T,B)>}impl<T,B>Collect<T,B>where T:Scan,B:FromIterator<<T as Scan>::Output>{pub fn new(size:usize)->Self{Self{size,_marker:PhantomData}}}impl<T,B>MarkedScan for Collect<T,B>where T:Scan,B:FromIterator<<T as Scan>::Output>{type Output=B;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{if self.size==0{iter.skip_whitespace();}repeat_with(| |<T as Scan>::scan(iter)).take(self.size).collect()}}#[derive(Debug,Copy,Clone)]pub struct SizedCollect<T,B=Vec<<T as Scan>::Output>>where T:Scan,B:FromIterator<<T as Scan>::Output>{_marker:PhantomData<fn()->(T,B)>}impl<T,B>Scan for SizedCollect<T,B>where T:Scan,B:FromIterator<<T as Scan>::Output>{type Output=B;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{let size=usize::scan(iter)?;if size==0{iter.skip_whitespace();}repeat_with(| |<T as Scan>::scan(iter)).take(size).collect()}}#[derive(Debug,Copy,Clone)]pub struct Splitted<T,P>where T:Scan{pat:P,_marker:PhantomData<fn()->T>}impl<T,P>Splitted<T,P>where T:Scan{pub fn new(pat:P)->Self{Self{pat,_marker:PhantomData}}}impl<T>MarkedScan for Splitted<T,char>where T:Scan{type Output=Vec<<T as Scan>::Output>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut iter=Scanner::new_from_iter(iter.next_token()?.split(self.pat));Some(from_fn(| |<T as Scan>::scan(&mut iter)).collect())}}impl<T>MarkedScan for Splitted<T,&str>where T:Scan{type Output=Vec<<T as Scan>::Output>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut iter=Scanner::new_from_iter(iter.next_token()?.split(self.pat));Some(from_fn(| |<T as Scan>::scan(&mut iter)).collect())}}impl<T,F>MarkedScan for F where F:Fn(&str)->Option<T>{type Output=T;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{self(iter.next_token()?)}}}
// codesnip-guard: tree_order
#[cfg_attr(any(),rustfmt::skip)]impl<D>SparseGraph<D>where D:SparseGraphConstruction{#[doc=" (order, parents)"]pub fn tree_order(&self,root:usize)->(Vec<usize>,Vec<usize>){let n=self.vertices_size();let mut order=Vec::with_capacity(n);let mut parents=vec![!0usize;n];let mut stack=Vec::with_capacity(n);stack.push(root);while let Some(u)=stack.pop(){order.push(u);for a in self.neighbors(u).rev(){if a.to!=parents[u]{parents[a.to]=u;stack.push(a.to);}}}(order,parents)}}