// codesnip-guard: HeavyLightDecomposition
#[cfg_attr(any(),rustfmt::skip)]pub use self::heavy_light_decomposition::{HeavyLightDecomposition,HeavyLightPathFold};#[cfg_attr(any(),rustfmt::skip)]mod heavy_light_decomposition{use super::{CartesianTree,Graph,Monoid,UndirectedSparseGraph};use std::ops::Range;#[derive(Clone,Debug)]pub struct HeavyLightDecomposition{nodes:Vec<HeavyLightNode>,order:Vec<usize>}#[derive(Clone,Copy,Debug)]struct HeavyLightNode{parent:u32,size:u32,head:u32,index:u32}impl UndirectedSparseGraph{pub fn hld(&self,root:usize)->HeavyLightDecomposition{HeavyLightDecomposition::new(root,self)}}impl HeavyLightDecomposition{pub fn new(root:usize,graph:&UndirectedSparseGraph)->Self{let n=graph.vertices_size();assert!(n<=u32::MAX as usize);let mut self_=Self{nodes:vec![HeavyLightNode{parent:n as u32,size:1,head:n as u32,index:0};n],order:Vec::with_capacity(n)};self_.order.push(root);for i in 0..n{let u=self_.order[i];for a in graph.neighbors(u){if a.to!=self_.nodes[u].parent as usize{self_.nodes[a.to].parent=u as u32;self_.order.push(a.to);}}}for&u in self_.order.iter().skip(1).rev(){let p=self_.nodes[u].parent as usize;self_.nodes[p].size+=self_.nodes[u].size;let heavy=self_.nodes[p].head as usize;if heavy==n||self_.nodes[heavy].size<=self_.nodes[u].size{self_.nodes[p].head=u as u32;}}self_.order.clear();let mut stack=vec![root];while let Some(head)=stack.pop(){let chain_start=self_.order.len()as u32;let chain_parent=self_.nodes[head].parent;let mut u=head;while u!=n{let heavy=self_.nodes[u].head as usize;let parent=self_.nodes[u].parent as usize;self_.nodes[u].head=chain_start;self_.nodes[u].parent=chain_parent;self_.nodes[u].index=self_.order.len()as u32;self_.order.push(u);for a in graph.neighbors(u).rev(){if a.to!=parent&&a.to!=heavy{stack.push(a.to);}}u=heavy;}}self_}#[inline]pub fn len(&self)->usize{self.order.len()}#[inline]pub fn is_empty(&self)->bool{self.order.is_empty()}#[inline]pub fn root(&self)->usize{self.order[0]}#[inline]pub fn parent(&self,v:usize)->Option<usize>{let index=self.nodes[v].index as usize;if index==self.nodes[v].head as usize{((self.nodes[v].parent as usize)<self.len()).then_some(self.nodes[v].parent as usize)}else{Some(self.order[index-1])}}#[inline]pub fn index(&self,v:usize)->usize{self.nodes[v].index as usize}#[inline]pub fn vertex(&self,index:usize)->usize{self.order[index]}#[inline]pub fn subtree_size(&self,v:usize)->usize{self.nodes[v].size as usize}#[inline]pub fn subtree_range(&self,v:usize)->Range<usize>{self.nodes[v].index as usize..self.nodes[v].index as usize+self.nodes[v].size as usize}#[inline]pub fn is_ancestor(&self,ancestor:usize,v:usize)->bool{self.subtree_range(ancestor).contains(&(self.nodes[v].index as usize))}#[inline]pub fn kth_ancestor(&self,mut v:usize,mut k:usize)->Option<usize>{loop{let head=self.nodes[v].head as usize;let chain_len=self.nodes[v].index as usize-head;if k<=chain_len{return Some(self.order[self.nodes[v].index as usize-k]);}k-=chain_len+1;v=self.nodes[v].parent as usize;if v==self.len(){return None;}}}#[inline]pub fn lca(&self,mut u:usize,mut v:usize)->usize{while self.nodes[u].head!=self.nodes[v].head{if self.nodes[u].index>self.nodes[v].index{u=self.nodes[u].parent as usize;}else{v=self.nodes[v].parent as usize;}}if self.nodes[u].index<self.nodes[v].index{u}else{v}}#[inline]pub fn distance(&self,u:usize,v:usize)->usize{let(up,down)=self.path_lengths(u,v);up+down}#[inline]pub fn jump(&self,u:usize,v:usize,mut k:usize)->Option<usize>{let target=v;let mut u=self.nodes[u];let mut v=self.nodes[v];let mut down=0;while u.head!=v.head{if u.index>v.index{let up=u.index as usize-u.head as usize+1;if k<up{return Some(self.order[u.index as usize-k]);}k-=up;u=self.nodes[u.parent as usize];}else{down+=v.index as usize-v.head as usize+1;v=self.nodes[v.parent as usize];}}if u.index>=v.index{let up=u.index as usize-v.index as usize;if k<=up{return Some(self.order[u.index as usize-k]);}k-=up;}else{down+=v.index as usize-u.index as usize;}down.checked_sub(k).and_then(|k|self.kth_ancestor(target,k))}#[inline]fn path_lengths(&self,mut u:usize,mut v:usize)->(usize,usize){let(mut up,mut down)=(0,0);while self.nodes[u].head!=self.nodes[v].head{if self.nodes[u].index>self.nodes[v].index{up+=self.nodes[u].index as usize-self.nodes[u].head as usize+1;u=self.nodes[u].parent as usize;}else{down+=self.nodes[v].index as usize-self.nodes[v].head as usize+1;v=self.nodes[v].parent as usize;}}if self.nodes[u].index>self.nodes[v].index{up+=self.nodes[u].index as usize-self.nodes[v].index as usize;}else{down+=self.nodes[v].index as usize-self.nodes[u].index as usize;}(up,down)}#[doc=" Calls `f` once for each nonempty DFS-index range on the vertex path."]#[doc=" The callback order is unspecified."]#[inline]pub fn path_vertices<F:FnMut(usize,usize)>(&self,u:usize,v:usize,f:F){self.path(u,v,false,f);}#[doc=" Calls `f` once for each nonempty DFS-index range on the edge path."]#[doc=" Each index represents the deeper endpoint of an edge. The callback order is unspecified."]#[inline]pub fn path_edges<F:FnMut(usize,usize)>(&self,u:usize,v:usize,f:F){self.path(u,v,true,f);}#[inline]fn path<F:FnMut(usize,usize)>(&self,mut u:usize,mut v:usize,is_edge:bool,mut f:F){loop{if self.nodes[u].index>self.nodes[v].index{std::mem::swap(&mut u,&mut v);}if self.nodes[u].head==self.nodes[v].head{break;}f(self.nodes[v].head as usize,self.nodes[v].index as usize+1);v=self.nodes[v].parent as usize;}let l=self.nodes[u].index as usize+usize::from(is_edge);let r=self.nodes[v].index as usize+1;if l<r{f(l,r);}}#[doc=" Folds a vertex path in `u`-to-`v` order."]#[doc=" `forward` folds a DFS-index range from left to right, and `reverse` folds it from right to"]#[doc=" left."]#[inline]pub fn fold_vertices<M:Monoid,F1:FnMut(usize,usize)->M::T,F2:FnMut(usize,usize)->M::T>(&self,u:usize,v:usize,forward:F1,reverse:F2)->M::T{self.fold::<M,_,_>(u,v,false,forward,reverse)}#[doc=" Folds an edge path in `u`-to-`v` order."]#[doc=" Each index represents the deeper endpoint of an edge. `forward` folds a DFS-index range"]#[doc=" from left to right, and `reverse` folds it from right to left."]#[inline]pub fn fold_edges<M:Monoid,F1:FnMut(usize,usize)->M::T,F2:FnMut(usize,usize)->M::T>(&self,u:usize,v:usize,forward:F1,reverse:F2)->M::T{self.fold::<M,_,_>(u,v,true,forward,reverse)}#[inline]fn fold<M:Monoid,F1:FnMut(usize,usize)->M::T,F2:FnMut(usize,usize)->M::T>(&self,mut u:usize,mut v:usize,is_edge:bool,mut forward:F1,mut reverse:F2)->M::T{let(mut left,mut right)=(M::unit(),M::unit());while self.nodes[u].head!=self.nodes[v].head{if self.nodes[u].index>self.nodes[v].index{left=M::operate(&left,&reverse(self.nodes[u].head as usize,self.nodes[u].index as usize+1));u=self.nodes[u].parent as usize;}else{right=M::operate(&forward(self.nodes[v].head as usize,self.nodes[v].index as usize+1),&right);v=self.nodes[v].parent as usize;}}let middle=if self.nodes[u].index>self.nodes[v].index{reverse(self.nodes[v].index as usize+usize::from(is_edge),self.nodes[u].index as usize+1)}else{forward(self.nodes[u].index as usize+usize::from(is_edge),self.nodes[v].index as usize+1)};M::operate(&M::operate(&left,&middle),&right)}}pub struct HeavyLightPathFold<'a,M:Monoid>{tree:&'a HeavyLightDecomposition,nodes:Vec<PathFoldNode<M::T>>}struct PathFoldNode<T>{parent:u32,children:[u32;2],priority:u32,value:T,aggregate:[T;2],prefix:[T;2]}impl HeavyLightDecomposition{#[doc=" `values` is indexed by vertex, not by DFS index."]pub fn build_fold<M:Monoid>(&self,values:&[M::T])->HeavyLightPathFold<'_,M>{assert_eq!(values.len(),self.len());let mut fold=HeavyLightPathFold{tree:self,nodes:self.order.iter().map(|&v|PathFoldNode{parent:u32::MAX,children:[u32::MAX;2],priority:0,value:values[v].clone(),aggregate:[values[v].clone(),values[v].clone()],prefix:[values[v].clone(),values[v].clone()]}).collect()};let mut start=0;let mut priorities=Vec::new();let mut stack=Vec::new();while start<self.len(){let mut end=start+1;while end<self.len()&&self.nodes[self.order[end]].head as usize==start{end+=1;}priorities.clear();let mut sum=0usize;for i in start..end{let weight=self.subtree_size(self.order[i])-if i+1<end{self.subtree_size(self.order[i+1])}else{0};let priority=(sum^(sum+weight)).ilog2();sum+=weight;fold.nodes[i].priority=priority;priorities.push(std::cmp::Reverse(priority));}let cartesian=CartesianTree::new(&priorities);for i in start..end{let parent=cartesian.parents[i-start];fold.nodes[i].parent=if parent==usize::MAX{u32::MAX}else{(parent+start)as u32};fold.nodes[i].children=cartesian.children[i-start].map(|v|{if v==usize::MAX{u32::MAX}else{(v+start)as u32}});}stack.clear();stack.push(cartesian.root+start);let mut i=0;while i<stack.len(){stack.extend(fold.nodes[stack[i]].children.into_iter().filter(|&v|v!=u32::MAX).map(|v|v as usize));i+=1;}for&i in stack.iter().rev(){fold.pull(i);}start=end;}fold}}impl<M:Monoid>HeavyLightPathFold<'_,M>{#[inline(always)]fn pull(&mut self,i:usize){let[l,r]=self.nodes[i].children.map(|v|{if v==u32::MAX{usize::MAX}else{v as usize}});self.nodes[i].prefix=if l==usize::MAX{[self.nodes[i].value.clone(),self.nodes[i].value.clone()]}else{[M::operate(&self.nodes[l].aggregate[0],&self.nodes[i].value),M::operate(&self.nodes[i].value,&self.nodes[l].aggregate[1])]};self.nodes[i].aggregate=if r==usize::MAX{self.nodes[i].prefix.clone()}else{[M::operate(&self.nodes[i].prefix[0],&self.nodes[r].aggregate[0]),M::operate(&self.nodes[r].aggregate[1],&self.nodes[i].prefix[1])]};}pub fn set(&mut self,vertex:usize,value:M::T){let mut i=self.tree.index(vertex);self.nodes[i].value=value;while i!=usize::MAX{self.pull(i);i=if self.nodes[i].parent==u32::MAX{usize::MAX}else{self.nodes[i].parent as usize};}}fn fold_prefix<const REVERSE:bool>(&self,k:usize)->M::T{let mut result=M::unit();let mut i=k;while i!=usize::MAX{if i<=k{result=if REVERSE{M::operate(&result,&self.nodes[i].prefix[1])}else{M::operate(&self.nodes[i].prefix[0],&result)};}i=if self.nodes[i].parent==u32::MAX{usize::MAX}else{self.nodes[i].parent as usize};}result}fn fold_range<const REVERSE:bool>(&self,l:usize,r:usize)->M::T{let(mut u,mut v)=(l,r);let(mut left,mut right)=(M::unit(),M::unit());while u!=v{if self.nodes[u].priority<self.nodes[v].priority{if u>=l{let child=self.nodes[u].children[1];if REVERSE{left=M::operate(&self.nodes[u].value,&left);if child!=u32::MAX{left=M::operate(&self.nodes[child as usize].aggregate[1],&left);}}else{left=M::operate(&left,&self.nodes[u].value);if child!=u32::MAX{left=M::operate(&left,&self.nodes[child as usize].aggregate[0]);}}}u=self.nodes[u].parent as usize;}else{if v<=r{right=if REVERSE{M::operate(&right,&self.nodes[v].prefix[1])}else{M::operate(&self.nodes[v].prefix[0],&right)};}v=self.nodes[v].parent as usize;}}if REVERSE{M::operate(&M::operate(&right,&self.nodes[u].value),&left)}else{M::operate(&M::operate(&left,&self.nodes[u].value),&right)}}#[doc=" Folds the vertex values in `u`-to-`v` order."]#[inline(always)]pub fn fold_vertices(&self,mut u:usize,mut v:usize)->M::T{let(mut left,mut right)=(M::unit(),M::unit());while self.tree.nodes[u].head!=self.tree.nodes[v].head{if self.tree.index(u)>self.tree.index(v){left=M::operate(&left,&self.fold_prefix::<true>(self.tree.index(u)));u=self.tree.nodes[u].parent as usize;}else{right=M::operate(&self.fold_prefix::<false>(self.tree.index(v)),&right);v=self.tree.nodes[v].parent as usize;}}let middle=if self.tree.index(u)>self.tree.index(v){self.fold_range::<true>(self.tree.index(v),self.tree.index(u))}else{self.fold_range::<false>(self.tree.index(u),self.tree.index(v))};M::operate(&M::operate(&left,&middle),&right)}}}
// codesnip-guard: CartesianTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::cartesian_tree::CartesianTree;#[cfg_attr(any(),rustfmt::skip)]mod cartesian_tree{use std::ops::Range;#[derive(Debug,Clone)]pub struct CartesianTree{pub root:usize,pub parents:Vec<usize>,pub children:Vec<[usize;2]>}impl CartesianTree{pub fn new<T>(a:&[T])->Self where T:PartialOrd{let mut parents=vec![!0;a.len()];let mut children=vec![[!0;2];a.len()];let mut root=!0;for i in 0..a.len(){let mut prev=!0;let mut parent=i.wrapping_sub(1);while parent!=!0&&a[i]<a[parent]{prev=parent;parent=parents[parent];}parents[i]=parent;if parent!=!0{children[parent][1]=i;}else{root=i;}if prev!=!0{parents[prev]=i;children[i][0]=prev;}}Self{root,parents,children}}pub fn with_ranges(&self,mut f:impl FnMut(usize,Range<usize>)){let mut stack=vec![(self.root,0,self.parents.len())];while let Some((v,l,r))=stack.pop(){f(v,l..r);if self.children[v][1]!=!0{stack.push((self.children[v][1],v+1,r));}if self.children[v][0]!=!0{stack.push((self.children[v][0],l,v));}}}}}
// 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()?)}}}