// codesnip-guard: tree_diameter
#[cfg_attr(any(),rustfmt::skip)]mod tree_diameter{use super::{EdgeListGraph,XorLinkedRootedTree,Zero};impl EdgeListGraph{#[doc=" `(diameter, vertex_path)` for a nonempty undirected tree; `weight` maps edge IDs to nonnegative values."]pub fn tree_diameter<T>(&self,weight:impl Fn(&usize)->T)->(T,Vec<usize>)where T:Clone+Ord+Zero+std::ops::Add<Output=T>{let n=self.vertices_size();let mut parent=vec![!0;n];let mut farthest:Vec<_>=(0..n).map(|u|(T::zero(),u)).collect();let(mut diameter,mut left,mut right,mut center)=(T::zero(),0,0,0);XorLinkedRootedTree::builder(n).with_eindexed().run(0,self.edges().copied(),|u,p,e|{parent[u]=p;let distance=farthest[u].0 .clone()+weight(&e);let candidate=distance.clone()+farthest[p].0 .clone();if diameter<candidate{diameter=candidate;left=farthest[u].1;right=farthest[p].1;center=p;}if farthest[p].0<distance{farthest[p]=(distance,farthest[u].1);}});let mut path=Vec::new();while left!=center{path.push(left);left=parent[left];}path.push(center);let middle=path.len();while right!=center{path.push(right);right=parent[right];}path[middle..].reverse();(diameter,path)}}}
// codesnip-guard: EdgeListGraph
#[cfg_attr(any(),rustfmt::skip)]pub use self::edge_list::{EdgeListGraph,EdgeListGraphScanner};#[cfg_attr(any(),rustfmt::skip)]mod edge_list{use super::{MarkedScan,Scan,ScanSource};use std::{marker::PhantomData,ops::Range,slice::Iter};#[derive(Clone,Debug)]#[doc=" Graph represented by a list of edges."]pub struct EdgeListGraph{vsize:usize,edges:Vec<(usize,usize)>}impl EdgeListGraph{#[doc=" Construct empty graph."]pub fn new(vsize:usize)->Self{Self{vsize,edges:Vec::new()}}#[doc=" Return the number of vertices."]pub fn vertices_size(&self)->usize{self.vsize}#[doc=" Return the number of edges."]pub fn edges_size(&self)->usize{self.edges.len()}#[doc=" Return an iterator over graph vertices."]pub fn vertices(&self)->Range<usize>{0..self.vertices_size()}pub fn edges(&self)->Iter<'_,(usize,usize)>{self.edges.iter()}#[doc=" Construct graph from edges."]pub fn from_edges(vsize:usize,edges:Vec<(usize,usize)>)->Self{Self{vsize,edges}}}impl std::ops::Index<usize>for EdgeListGraph{type Output=(usize,usize);fn index(&self,index:usize)->&Self::Output{&self.edges[index]}}pub struct EdgeListGraphScanner<U:Scan<Output=usize>,T:Scan>{vsize:usize,esize:usize,_marker:PhantomData<fn()->(U,T)>}impl<U:Scan<Output=usize>,T:Scan>EdgeListGraphScanner<U,T>{pub fn new(vsize:usize,esize:usize)->Self{Self{vsize,esize,_marker:PhantomData}}}impl<U:Scan<Output=usize>,T:Scan>MarkedScan for EdgeListGraphScanner<U,T>{type Output=(EdgeListGraph,Vec<<T as Scan>::Output>);fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut edges=Vec::with_capacity(self.esize);let mut rest=Vec::with_capacity(self.esize);for _ in 0..self.esize{edges.push((U::scan(iter)?,U::scan(iter)?));rest.push(T::scan(iter)?);}let graph=EdgeListGraph::from_edges(self.vsize,edges);Some((graph,rest))}}}
// codesnip-guard: XorLinkedRootedTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::xor_linked_tree::*;#[cfg_attr(any(),rustfmt::skip)]mod xor_linked_tree{use super::{MarkedScan,Scan,ScanSource};use std::{marker::PhantomData,ops::Range};type Marker<T>=PhantomData<fn()->T>;type BuilderMarker<P,D,H,PE,EC,X,B,E>=Marker<((P,D,H),(PE,EC),(X,B,E))>;type ScannerMarker<U,T,P,D,H,PE,EC,X,B,E>=Marker<((U,T),(P,D,H),(PE,EC),(X,B,E))>;#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoParent{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum RecordParent{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoDfsPreorder{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum RecordDfsPreorder{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoDepth{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum RecordDepth{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoParentEdge{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum RecordParentEdge{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoEdgeChild{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum RecordEdgeChild{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoEIndexed{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum EIndexed{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum NoXorBottomUpOrder{}#[derive(Clone,Copy,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)]pub enum RecordXorBottomUpOrder{}pub trait ParentComponent{type Data;fn build(parent:Vec<usize>)->Self::Data;}impl ParentComponent for NoParent{type Data=();fn build(_parent:Vec<usize>){}}impl ParentComponent for RecordParent{type Data=Vec<usize>;fn build(parent:Vec<usize>)->Vec<usize>{parent}}pub trait XorBottomUpOrderBuffer{type Data;fn new(n:usize)->Self::Data;fn push(data:&mut Self::Data,v:usize);fn as_slice(data:&Self::Data)->&[usize];}impl XorBottomUpOrderBuffer for NoXorBottomUpOrder{type Data=();fn new(_n:usize){}fn push(_data:&mut Self::Data,_v:usize){}fn as_slice(_data:&Self::Data)->&[usize]{&[]}}impl XorBottomUpOrderBuffer for RecordXorBottomUpOrder{type Data=Vec<usize>;fn new(n:usize)->Vec<usize>{Vec::with_capacity(n.saturating_sub(1))}fn push(data:&mut Vec<usize>,v:usize){data.push(v);}fn as_slice(data:&Vec<usize>)->&[usize]{data}}pub trait XorBottomUpOrderComponent{type Data;}impl XorBottomUpOrderComponent for NoXorBottomUpOrder{type Data=();}impl XorBottomUpOrderComponent for RecordXorBottomUpOrder{type Data=Vec<usize>;}pub trait BuildXorBottomUpOrder<B>:XorBottomUpOrderComponent where B:XorBottomUpOrderBuffer{fn build(buffer:B::Data)->Self::Data;}impl<B>BuildXorBottomUpOrder<B>for NoXorBottomUpOrder where B:XorBottomUpOrderBuffer{fn build(_buffer:B::Data){}}impl BuildXorBottomUpOrder<RecordXorBottomUpOrder>for RecordXorBottomUpOrder{fn build(buffer:Vec<usize>)->Vec<usize>{buffer}}#[derive(Debug)]pub struct DfsPreorder{order:Vec<usize>,preorder_index:Vec<usize>,subtree_end:Vec<usize>}pub trait DfsPreorderComponent{type Data;fn build(n:usize,root:usize,parent:&[usize],xor_order:&[usize])->Self::Data;}impl DfsPreorderComponent for NoDfsPreorder{type Data=();fn build(_n:usize,_root:usize,_parent:&[usize],_xor_order:&[usize]){}}impl DfsPreorderComponent for RecordDfsPreorder{type Data=DfsPreorder;fn build(n:usize,root:usize,parent:&[usize],xor_order:&[usize])->DfsPreorder{let mut preorder_index=vec![1usize;n];for&v in xor_order{preorder_index[parent[v]]+=preorder_index[v];}let mut subtree_end=vec![0usize;n];if n!=0{subtree_end[root]=n;}for&v in xor_order.iter().rev(){let p=parent[v];let size=preorder_index[v];let r=preorder_index[p];subtree_end[v]=r;preorder_index[v]=r;preorder_index[p]=r-size;}for i in&mut preorder_index{*i-=1;}let mut order=vec![0usize;n];for v in 0..n{order[preorder_index[v]]=v;}DfsPreorder{order,preorder_index,subtree_end}}}pub trait DepthComponent{type Data;fn build(n:usize,root:usize,parent:&[usize],xor_order:&[usize])->Self::Data;}impl DepthComponent for NoDepth{type Data=();fn build(_n:usize,_root:usize,_parent:&[usize],_xor_order:&[usize]){}}impl DepthComponent for RecordDepth{type Data=Vec<usize>;fn build(n:usize,_root:usize,parent:&[usize],xor_order:&[usize])->Vec<usize>{let mut depth=vec![0usize;n];for&v in xor_order.iter().rev(){depth[v]=depth[parent[v]]+1;}depth}}pub trait ParentEdgeComponent{type Data;fn build(parent_edge:Vec<usize>)->Self::Data;}impl ParentEdgeComponent for NoParentEdge{type Data=();fn build(_parent_edge:Vec<usize>){}}impl ParentEdgeComponent for RecordParentEdge{type Data=Vec<usize>;fn build(parent_edge:Vec<usize>)->Vec<usize>{parent_edge}}pub trait EdgeChildComponent{type Data;fn new(m:usize)->Self::Data;fn set(data:&mut Self::Data,eid:usize,child:usize);}impl EdgeChildComponent for NoEdgeChild{type Data=();fn new(_m:usize){}fn set(_data:&mut Self::Data,_eid:usize,_child:usize){}}impl EdgeChildComponent for RecordEdgeChild{type Data=Vec<usize>;fn new(m:usize)->Vec<usize>{vec![0usize;m]}fn set(data:&mut Vec<usize>,eid:usize,child:usize){data[eid]=child;}}pub struct XorLinkedRootedTree<P=NoParent,D=NoDfsPreorder,H=NoDepth,PE=NoParentEdge,EC=NoEdgeChild,X=NoXorBottomUpOrder>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,X:XorBottomUpOrderComponent{n:usize,root:usize,parent:P::Data,dfs:D::Data,depth:H::Data,parent_edge:PE::Data,edge_child:EC::Data,xor_order:X::Data,_marker:Marker<(P,D,H,PE,EC,X)>}pub struct XorLinkedRootedTreeBuilder<P=NoParent,D=NoDfsPreorder,H=NoDepth,PE=NoParentEdge,EC=NoEdgeChild,X=NoXorBottomUpOrder,B=NoXorBottomUpOrder,E=NoEIndexed>{n:usize,_marker:BuilderMarker<P,D,H,PE,EC,X,B,E>}impl XorLinkedRootedTree{pub fn builder(n:usize)->XorLinkedRootedTreeBuilder{XorLinkedRootedTreeBuilder{n,_marker:PhantomData}}}impl<P,D,H,PE,EC,X,B,E>XorLinkedRootedTreeBuilder<P,D,H,PE,EC,X,B,E>{pub fn with_parent(self)->XorLinkedRootedTreeBuilder<RecordParent,D,H,PE,EC,X,B,E>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}pub fn with_dfs_preorder(self)->XorLinkedRootedTreeBuilder<P,RecordDfsPreorder,H,PE,EC,X,RecordXorBottomUpOrder,E>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}pub fn with_depth(self)->XorLinkedRootedTreeBuilder<P,D,RecordDepth,PE,EC,X,RecordXorBottomUpOrder,E>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}pub fn with_xor_bottom_up_order(self)->XorLinkedRootedTreeBuilder<P,D,H,PE,EC,RecordXorBottomUpOrder,RecordXorBottomUpOrder,E>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}}impl<P,D,H,X,B>XorLinkedRootedTreeBuilder<P,D,H,NoParentEdge,NoEdgeChild,X,B,NoEIndexed>{pub fn with_eindexed(self)->XorLinkedRootedTreeBuilder<P,D,H,NoParentEdge,NoEdgeChild,X,B,EIndexed>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}}impl<P,D,H,PE,EC,X,B>XorLinkedRootedTreeBuilder<P,D,H,PE,EC,X,B,EIndexed>{pub fn with_parent_edge(self)->XorLinkedRootedTreeBuilder<P,D,H,RecordParentEdge,EC,X,B,EIndexed>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}pub fn with_edge_child(self)->XorLinkedRootedTreeBuilder<P,D,H,PE,RecordEdgeChild,X,B,EIndexed>{XorLinkedRootedTreeBuilder{n:self.n,_marker:PhantomData}}}impl<P,D,H,X,B>XorLinkedRootedTreeBuilder<P,D,H,NoParentEdge,NoEdgeChild,X,B,NoEIndexed>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{#[doc=" Builds a tree rooted at 0. The `n - 1` parents are in vertex order,"]#[doc=" and the parent of vertex `v` must be less than `v`."]pub fn build_from_ordered_parents(self,parents:impl IntoIterator<Item=usize>)->XorLinkedRootedTree<P,D,H,NoParentEdge,NoEdgeChild,X>{let mut parent=Vec::with_capacity(self.n);if self.n!=0{parent.push(usize::MAX);}parent.extend(parents);assert_eq!(parent.len(),self.n);let mut order=B::new(self.n);for v in(1..self.n).rev(){B::push(&mut order,v);}finish_rooted_tree::<P,D,H,X,B>(0,parent,order)}pub fn build<I>(self,root:usize,edges:I)->XorLinkedRootedTree<P,D,H,NoParentEdge,NoEdgeChild,X>where I:IntoIterator<Item=(usize,usize)>{let mut acc=XorAccumulator::new(self.n);for(u,v)in edges{acc.add_edge(u,v);}finish_accumulator::<P,D,H,X,B>(self.n,root,acc)}}impl<P,D,H,PE,EC,X,B>XorLinkedRootedTreeBuilder<P,D,H,PE,EC,X,B,EIndexed>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{pub fn build<I>(self,root:usize,edges:I)->XorLinkedRootedTree<P,D,H,PE,EC,X>where I:IntoIterator<Item=(usize,usize)>{let mut acc=XorEIndexedAccumulator::new(self.n);for(eid,(u,v))in edges.into_iter().enumerate(){acc.add_edge(eid,u,v);}finish_eindexed_accumulator::<P,D,H,PE,EC,X,B>(self.n,root,acc)}}impl XorLinkedRootedTreeBuilder{pub fn run<I,F>(self,root:usize,edges:I,f:F)where I:IntoIterator<Item=(usize,usize)>,F:FnMut(usize,usize){let mut acc=XorAccumulator::new(self.n);for(u,v)in edges{acc.add_edge(u,v);}let mut order=();acc.finish::<NoXorBottomUpOrder,_>(root,&mut order,f);}}impl XorLinkedRootedTreeBuilder<NoParent,NoDfsPreorder,NoDepth,NoParentEdge,NoEdgeChild,NoXorBottomUpOrder,NoXorBottomUpOrder,EIndexed>{pub fn run<I,F>(self,root:usize,edges:I,f:F)where I:IntoIterator<Item=(usize,usize)>,F:FnMut(usize,usize,usize){let mut acc=XorEIndexedAccumulator::new(self.n);for(eid,(u,v))in edges.into_iter().enumerate(){acc.add_edge(eid,u,v);}let mut order=();let mut edge_child=();acc.finish::<NoXorBottomUpOrder,NoEdgeChild,_>(root,&mut order,&mut edge_child,f);}}impl<P,D,H,PE,EC,O>XorLinkedRootedTree<P,D,H,PE,EC,O>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,O:XorBottomUpOrderComponent{pub fn vertices_size(&self)->usize{self.n}pub fn edges_size(&self)->usize{self.n.saturating_sub(1)}pub fn root(&self)->usize{self.root}}impl<D,H,PE,EC,O>XorLinkedRootedTree<RecordParent,D,H,PE,EC,O>where D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,O:XorBottomUpOrderComponent{pub fn parent(&self,v:usize)->usize{self.parent[v]}pub fn parents(&self)->&[usize]{&self.parent}}impl<P,D,H,PE,EC>XorLinkedRootedTree<P,D,H,PE,EC,RecordXorBottomUpOrder>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent{#[doc=" Returns the bottom-up XOR order, excluding the root."]pub fn xor_bottom_up_order(&self)->&[usize]{&self.xor_order}#[doc=" Returns the top-down XOR order, excluding the root."]pub fn xor_top_down_order(&self)->impl DoubleEndedIterator<Item=usize>+ExactSizeIterator+'_{self.xor_order.iter().rev().copied()}}impl<P,H,PE,EC,O>XorLinkedRootedTree<P,RecordDfsPreorder,H,PE,EC,O>where P:ParentComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,O:XorBottomUpOrderComponent{pub fn dfs_order(&self)->&[usize]{&self.dfs.order}pub fn dfs_index(&self,v:usize)->usize{self.dfs.preorder_index[v]}pub fn subtree_size(&self,v:usize)->usize{self.dfs.subtree_end[v]-self.dfs.preorder_index[v]}pub fn subtree_range(&self,v:usize)->Range<usize>{self.dfs.preorder_index[v]..self.dfs.subtree_end[v]}pub fn children(&self,v:usize)->Children<'_>{Children{dfs:&self.dfs,next:self.dfs.preorder_index[v]+1,end:self.dfs.subtree_end[v]}}}impl<P,D,PE,EC,O>XorLinkedRootedTree<P,D,RecordDepth,PE,EC,O>where P:ParentComponent,D:DfsPreorderComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,O:XorBottomUpOrderComponent{pub fn depth(&self,v:usize)->usize{self.depth[v]}pub fn depths(&self)->&[usize]{&self.depth}}impl<P,D,H,EC,O>XorLinkedRootedTree<P,D,H,RecordParentEdge,EC,O>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,EC:EdgeChildComponent,O:XorBottomUpOrderComponent{pub fn parent_edge(&self,v:usize)->usize{self.parent_edge[v]}pub fn parent_edges(&self)->&[usize]{&self.parent_edge}}impl<P,D,H,PE,O>XorLinkedRootedTree<P,D,H,PE,RecordEdgeChild,O>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,O:XorBottomUpOrderComponent{pub fn edge_child(&self,eid:usize)->usize{self.edge_child[eid]}pub fn edge_children(&self)->&[usize]{&self.edge_child}}pub struct Children<'a>{dfs:&'a DfsPreorder,next:usize,end:usize}impl Iterator for Children<'_>{type Item=usize;fn next(&mut self)->Option<usize>{if self.next==self.end{None}else{let v=self.dfs.order[self.next];self.next=self.dfs.subtree_end[v];Some(v)}}}pub struct XorLinkedRootedTreeScanner<U,T=(),P=NoParent,D=NoDfsPreorder,H=NoDepth,PE=NoParentEdge,EC=NoEdgeChild,X=NoXorBottomUpOrder,B=NoXorBottomUpOrder,E=NoEIndexed>where U:Scan<Output=usize>,T:Scan{n:usize,root:usize,_marker:ScannerMarker<U,T,P,D,H,PE,EC,X,B,E>}impl<U,T>XorLinkedRootedTreeScanner<U,T>where U:Scan<Output=usize>,T:Scan{pub fn new(n:usize,root:usize)->Self{Self{n,root,_marker:PhantomData}}}impl<U,T,P,D,H,PE,EC,X,B,E>XorLinkedRootedTreeScanner<U,T,P,D,H,PE,EC,X,B,E>where U:Scan<Output=usize>,T:Scan{pub fn with_parent(self)->XorLinkedRootedTreeScanner<U,T,RecordParent,D,H,PE,EC,X,B,E>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}pub fn with_dfs_preorder(self)->XorLinkedRootedTreeScanner<U,T,P,RecordDfsPreorder,H,PE,EC,X,RecordXorBottomUpOrder,E>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}pub fn with_depth(self)->XorLinkedRootedTreeScanner<U,T,P,D,RecordDepth,PE,EC,X,RecordXorBottomUpOrder,E>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}pub fn with_xor_bottom_up_order(self)->XorLinkedRootedTreeScanner<U,T,P,D,H,PE,EC,RecordXorBottomUpOrder,RecordXorBottomUpOrder,E>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}}impl<U,T,P,D,H,X,B>XorLinkedRootedTreeScanner<U,T,P,D,H,NoParentEdge,NoEdgeChild,X,B,NoEIndexed>where U:Scan<Output=usize>,T:Scan{pub fn with_eindexed(self)->XorLinkedRootedTreeScanner<U,T,P,D,H,NoParentEdge,NoEdgeChild,X,B,EIndexed>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}}impl<U,T,P,D,H,PE,EC,X,B>XorLinkedRootedTreeScanner<U,T,P,D,H,PE,EC,X,B,EIndexed>where U:Scan<Output=usize>,T:Scan{pub fn with_parent_edge(self)->XorLinkedRootedTreeScanner<U,T,P,D,H,RecordParentEdge,EC,X,B,EIndexed>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}pub fn with_edge_child(self)->XorLinkedRootedTreeScanner<U,T,P,D,H,PE,RecordEdgeChild,X,B,EIndexed>{XorLinkedRootedTreeScanner{n:self.n,root:self.root,_marker:PhantomData}}}impl<U,T,P,D,H,X,B>MarkedScan for XorLinkedRootedTreeScanner<U,T,P,D,H,NoParentEdge,NoEdgeChild,X,B,NoEIndexed>where U:Scan<Output=usize>,T:Scan,P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{type Output=(XorLinkedRootedTree<P,D,H,NoParentEdge,NoEdgeChild,X>,Vec<<T as Scan>::Output>);fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut acc=XorAccumulator::new(self.n);let mut weights=Vec::with_capacity(self.n.saturating_sub(1));for _ in 0..self.n.saturating_sub(1){let u=U::scan(iter)?;let v=U::scan(iter)?;acc.add_edge(u,v);weights.push(T::scan(iter)?);}Some((finish_accumulator::<P,D,H,X,B>(self.n,self.root,acc),weights))}}impl<U,T,P,D,H,PE,EC,X,B>MarkedScan for XorLinkedRootedTreeScanner<U,T,P,D,H,PE,EC,X,B,EIndexed>where U:Scan<Output=usize>,T:Scan,P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{type Output=(XorLinkedRootedTree<P,D,H,PE,EC,X>,Vec<<T as Scan>::Output>);fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut acc=XorEIndexedAccumulator::new(self.n);let mut weights=Vec::with_capacity(self.n.saturating_sub(1));for eid in 0..self.n.saturating_sub(1){let u=U::scan(iter)?;let v=U::scan(iter)?;acc.add_edge(eid,u,v);weights.push(T::scan(iter)?);}Some((finish_eindexed_accumulator::<P,D,H,PE,EC,X,B>(self.n,self.root,acc),weights))}}fn finish_accumulator<P,D,H,X,B>(n:usize,root:usize,acc:XorAccumulator)->XorLinkedRootedTree<P,D,H,NoParentEdge,NoEdgeChild,X>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{let mut xor_order=B::new(n);let parent=acc.finish::<B,_>(root,&mut xor_order,|_,_|{});finish_rooted_tree::<P,D,H,X,B>(root,parent,xor_order)}fn finish_rooted_tree<P,D,H,X,B>(root:usize,parent:Vec<usize>,xor_order:B::Data)->XorLinkedRootedTree<P,D,H,NoParentEdge,NoEdgeChild,X>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{let n=parent.len();let order=B::as_slice(&xor_order);let dfs=D::build(n,root,&parent,order);let depth=H::build(n,root,&parent,order);XorLinkedRootedTree{n,root,parent:P::build(parent),dfs,depth,parent_edge:(),edge_child:(),xor_order:X::build(xor_order),_marker:PhantomData}}fn finish_eindexed_accumulator<P,D,H,PE,EC,X,B>(n:usize,root:usize,acc:XorEIndexedAccumulator)->XorLinkedRootedTree<P,D,H,PE,EC,X>where P:ParentComponent,D:DfsPreorderComponent,H:DepthComponent,PE:ParentEdgeComponent,EC:EdgeChildComponent,X:BuildXorBottomUpOrder<B>,B:XorBottomUpOrderBuffer{let mut xor_order=B::new(n);let mut edge_child=EC::new(n.saturating_sub(1));let(parent,parent_edge)=acc.finish::<B,EC,_>(root,&mut xor_order,&mut edge_child,|_,_,_|{});let order=B::as_slice(&xor_order);let dfs=D::build(n,root,&parent,order);let depth=H::build(n,root,&parent,order);XorLinkedRootedTree{n,root,parent:P::build(parent),dfs,depth,parent_edge:PE::build(parent_edge),edge_child,xor_order:X::build(xor_order),_marker:PhantomData}}struct XorAccumulator{deg:Vec<isize>,xor:Vec<usize>}impl XorAccumulator{fn new(n:usize)->Self{Self{deg:vec![0;n],xor:vec![0;n]}}fn add_edge(&mut self,u:usize,v:usize){self.deg[u]+=1;self.deg[v]+=1;self.xor[u]^=v;self.xor[v]^=u;}fn finish<O,F>(mut self,root:usize,xor_order:&mut O::Data,mut f:F)->Vec<usize>where O:XorBottomUpOrderBuffer,F:FnMut(usize,usize){self.deg[root]=0;for i in 0..self.deg.len(){let mut v=i;while self.deg[v]==1{let p=self.xor[v];O::push(xor_order,v);f(v,p);self.deg[v]=0;self.deg[p]-=1;self.xor[p]^=v;v=p;}}self.xor[root]=usize::MAX;self.xor}}struct XorEIndexedAccumulator{deg:Vec<isize>,xor:Vec<usize>,edge_xor:Vec<usize>}impl XorEIndexedAccumulator{fn new(n:usize)->Self{Self{deg:vec![0;n],xor:vec![0;n],edge_xor:vec![0;n]}}fn add_edge(&mut self,eid:usize,u:usize,v:usize){self.deg[u]+=1;self.deg[v]+=1;self.xor[u]^=v;self.xor[v]^=u;self.edge_xor[u]^=eid;self.edge_xor[v]^=eid;}fn finish<O,EC,F>(mut self,root:usize,xor_order:&mut O::Data,edge_child:&mut EC::Data,mut f:F)->(Vec<usize>,Vec<usize>)where O:XorBottomUpOrderBuffer,EC:EdgeChildComponent,F:FnMut(usize,usize,usize){self.deg[root]=0;for i in 0..self.deg.len(){let mut v=i;while self.deg[v]==1{let p=self.xor[v];let e=self.edge_xor[v];O::push(xor_order,v);EC::set(edge_child,e,v);f(v,p,e);self.deg[v]=0;self.deg[p]-=1;self.xor[p]^=v;self.edge_xor[p]^=e;v=p;}}self.xor[root]=usize::MAX;self.edge_xor[root]=usize::MAX;(self.xor,self.edge_xor)}}}
// 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: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}