// codesnip-guard: steiner_tree
#[cfg_attr(any(),rustfmt::skip)]pub use self::steiner_tree::{SteinerTreeBuilder,SteinerTreeExt,SteinerTreeOutput,SteinerTreeParent,SteinerTreeParentPolicy};#[cfg_attr(any(),rustfmt::skip)]mod steiner_tree{use super::{AdditiveOperation,BitDpExt,Bounded,Graph,Monoid,PartialIgnoredOrd,ShortestPathSemiRing,UnionFind,VertexMap,Zero,shortest_path::{NoParent,OptionSp,RecordParent,StandardSp}};use std::{cmp::Reverse,collections::BinaryHeap,iter::repeat_with,marker::PhantomData,ops::Add};pub enum SteinerTreeParent<V,L>{None,Split(usize),Edge(V,L)}pub trait SteinerTreeParentPolicy<G:Graph>{type State;type Label;fn init(graph:&G)->Self::State;fn label(label:&G::Label)->Self::Label;fn save_split(graph:&G,state:&mut Self::State,vertex:G::Vertex,subset:usize);fn save_parent(graph:&G,state:&mut Self::State,from:G::Vertex,to:G::Vertex,label:Self::Label);}impl<G:Graph>SteinerTreeParentPolicy<G>for NoParent{type State=();type Label=();fn init(_graph:&G){}fn label(_label:&G::Label){}fn save_split(_graph:&G,_state:&mut(),_vertex:G::Vertex,_subset:usize){}fn save_parent(_graph:&G,_state:&mut(),_from:G::Vertex,_to:G::Vertex,_label:()){}}impl<G>SteinerTreeParentPolicy<G>for RecordParent where G:Graph<Label:Clone>+VertexMap<SteinerTreeParent<<G as Graph>::Vertex,<G as Graph>::Label>>{type State=<G as VertexMap<SteinerTreeParent<G::Vertex,G::Label>>>::Vmap;type Label=G::Label;fn init(graph:&G)->Self::State{graph.construct_vmap(| |SteinerTreeParent::None)}fn label(label:&G::Label)->Self::Label{label.clone()}fn save_split(graph:&G,state:&mut Self::State,vertex:G::Vertex,subset:usize){*graph.vmap_get_mut(state,vertex)=SteinerTreeParent::Split(subset);}fn save_parent(graph:&G,state:&mut Self::State,from:G::Vertex,to:G::Vertex,label:Self::Label){*graph.vmap_get_mut(state,to)=SteinerTreeParent::Edge(from,label);}}pub trait SteinerTreeExt:Graph{fn steiner_tree(&self)->SteinerTreeBuilder<'_,Self>where Self:Sized{SteinerTreeBuilder{graph:self,_marker:PhantomData}}}impl<G>SteinerTreeExt for G where G:Graph+?Sized{}pub struct SteinerTreeBuilder<'g,G,S=(),P=NoParent>where G:Graph,P:SteinerTreeParentPolicy<G>{graph:&'g G,_marker:PhantomData<fn()->(S,P)>}impl<'g,G,S,P>SteinerTreeBuilder<'g,G,S,P>where G:Graph,P:SteinerTreeParentPolicy<G>{pub fn with_sp<T>(self)->SteinerTreeBuilder<'g,G,T,P>where T:ShortestPathSemiRing{SteinerTreeBuilder{graph:self.graph,_marker:PhantomData}}pub fn with_standard_sp<M>(self)->SteinerTreeBuilder<'g,G,StandardSp<M>,P>where M:Monoid<T:Bounded+Ord>{self.with_sp()}pub fn with_standard_sp_additive<T>(self)->SteinerTreeBuilder<'g,G,StandardSp<AdditiveOperation<T>>,P>where T:Clone+Zero+Add<Output=T>+Bounded+Ord{self.with_sp()}pub fn with_option_sp<M>(self)->SteinerTreeBuilder<'g,G,OptionSp<M>,P>where M:Monoid<T:Ord>{self.with_sp()}pub fn with_option_sp_additive<T>(self)->SteinerTreeBuilder<'g,G,OptionSp<AdditiveOperation<T>>,P>where T:Clone+Zero+Add<Output=T>+Ord{self.with_sp()}}impl<'g,G,S>SteinerTreeBuilder<'g,G,S>where G:Graph{pub fn with_parent(self)->SteinerTreeBuilder<'g,G,S,RecordParent>where RecordParent:SteinerTreeParentPolicy<G>{SteinerTreeBuilder{graph:self.graph,_marker:PhantomData}}}impl<'g,G,S,P>SteinerTreeBuilder<'g,G,S,P>where G:Graph+VertexMap<S::T>,S:ShortestPathSemiRing,P:SteinerTreeParentPolicy<G>{#[doc=" Requires commutative multiplication and nonnegative edge weights."]pub fn solve<M,I>(&self,terminals:I,weight:M)->SteinerTreeOutput<'g,S,G,P>where M:Fn(G::Label)->S::T,I:ExactSizeIterator<Item=G::Vertex>{let graph=self.graph;let tsize=terminals.len();let states=if tsize==0{0}else{1<<tsize};let mut dp:Vec<_>=repeat_with(| |graph.construct_vmap(S::inf)).take(states).collect();let mut parent:Vec<_>=repeat_with(| |P::init(graph)).take(states).collect();for(i,t)in terminals.enumerate(){*graph.vmap_get_mut(&mut dp[1<<i],t)=S::source();}let inf=S::inf();for bit in 1..states{let(prev,current)=dp.split_at_mut(bit);let dp=&mut current[0];for sub in bit.subsets().skip(1).take_while(|&sub|sub>bit^sub){let left=&prev[sub];let right=&prev[bit^sub];for u in graph.vertices(){let left=graph.vmap_get(left,u);let right=graph.vmap_get(right,u);if left!=&inf&&right!=&inf{let cost=S::mul(left,right);if S::add_assign(graph.vmap_get_mut(dp,u),&cost){P::save_split(graph,&mut parent[bit],u,sub);}}}}let mut heap:BinaryHeap<_>=graph.vertices().filter_map(|u|{let d=graph.vmap_get(dp,u);(d!=&inf).then(| |PartialIgnoredOrd(Reverse(d.clone()),u))}).collect();while let Some(PartialIgnoredOrd(Reverse(d),u))=heap.pop(){if graph.vmap_get(dp,u)!=&d{continue;}for neighbor in graph.neighbors(u){let v=neighbor.to;let label=P::label(&neighbor.label);let nd=S::mul(&d,&weight(neighbor.label));if S::add_assign(graph.vmap_get_mut(dp,v),&nd){P::save_parent(graph,&mut parent[bit],u,v,label);heap.push(PartialIgnoredOrd(Reverse(nd),v));}}}}SteinerTreeOutput{graph,dp,parent}}}pub struct SteinerTreeOutput<'g,S,G,P=NoParent>where G:Graph+VertexMap<S::T>,S:ShortestPathSemiRing,P:SteinerTreeParentPolicy<G>{graph:&'g G,dp:Vec<<G as VertexMap<S::T>>::Vmap>,parent:Vec<P::State>}impl<S,G,P>SteinerTreeOutput<'_,S,G,P>where G:Graph+VertexMap<S::T>,S:ShortestPathSemiRing,P:SteinerTreeParentPolicy<G>{pub fn minimum_from_source(&self,source:G::Vertex)->S::T{match self.dp.last(){Some(dp)=>self.graph.vmap_get(dp,source).clone(),None=>S::source(),}}}impl<S,G>SteinerTreeOutput<'_,S,G,RecordParent>where G:Graph<Label:Clone>+VertexMap<S::T>+VertexMap<usize>+VertexMap<SteinerTreeParent<<G as Graph>::Vertex,<G as Graph>::Label>>,S:ShortestPathSemiRing{#[doc=" For undirected graphs with nonnegative additive weights."]#[doc=" Returns `None` when the terminals cannot be connected to `source`."]pub fn edges_from_source(&self,source:G::Vertex)->Option<Vec<G::Label>>{if self.dp.is_empty(){return Some(vec![]);}if self.minimum_from_source(source)==S::inf(){return None;}let graph=self.graph;let mut index=graph.construct_vmap(| |0usize);for(i,u)in graph.vertices().enumerate(){*graph.vmap_get_mut(&mut index,u)=i;}let mut uf=UnionFind::new(graph.vsize());let mut edges=vec![];let mut stack=vec![(self.dp.len()-1,source)];while let Some((bit,u))=stack.pop(){match graph.vmap_get(&self.parent[bit],u){SteinerTreeParent::None=>{}&SteinerTreeParent::Split(sub)=>{stack.push((sub,u));stack.push((bit^sub,u));}SteinerTreeParent::Edge(v,label)=>{if uf.unite(*graph.vmap_get(&index,u),*graph.vmap_get(&index,*v)){edges.push(label.clone());}stack.push((bit,*v));}}}Some(edges)}}}
// codesnip-guard: AdditiveOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::additive_operation_impl::AdditiveOperation;#[cfg_attr(any(),rustfmt::skip)]mod additive_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Add,Neg,Sub}};#[doc=" $+$"]pub struct AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()+y.clone()}}impl<T>Unital for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{#[inline]fn unit()->Self::T{Zero::zero()}}impl<T>Associative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Commutative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Invertible for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>+Sub<Output=T>+Neg<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{-x.clone()}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()-y.clone()}}}
// codesnip-guard: BitDp
#[cfg_attr(any(),rustfmt::skip)]pub use self::bitdp::{BitDpExt,Combinations,Subsets};#[cfg_attr(any(),rustfmt::skip)]mod bitdp{use super::{One,Zero};use std::ops::{Add,BitAnd,BitOr,BitXor,Div,Not,Shl,Shr,Sub};pub trait BitDpExt:Sized+Copy+Default+PartialEq+Eq+PartialOrd+Ord+Not<Output=Self>+BitAnd<Output=Self>+BitOr<Output=Self>+BitXor<Output=Self>+Shl<usize,Output=Self>+Shr<usize,Output=Self>+Add<Output=Self>+Sub<Output=Self>+Div<Output=Self>+Zero+One{fn contains(self,x:usize)->bool{self&(Self::one()<<x)!=Self::zero()}fn insert(self,x:usize)->Self{self|(Self::one()<<x)}fn remove(self,x:usize)->Self{self&!(Self::one()<<x)}fn is_subset(self,elements:Self)->bool{self&elements==elements}fn is_superset(self,elements:Self)->bool{elements.is_subset(self)}fn subsets(self)->Subsets<Self>{Subsets{mask:self,cur:Some(self)}}fn combinations(n:usize,k:usize)->Combinations<Self>{Combinations{mask:Self::one()<<n,cur:Some((Self::one()<<k)-Self::one())}}}impl BitDpExt for u8{}impl BitDpExt for u16{}impl BitDpExt for u32{}impl BitDpExt for u64{}impl BitDpExt for u128{}impl BitDpExt for usize{}#[derive(Debug,Clone)]pub struct Subsets<T>{mask:T,cur:Option<T>}impl<T>Iterator for Subsets<T>where T:BitDpExt{type Item=T;fn next(&mut self)->Option<Self::Item>{if let Some(cur)=self.cur{self.cur=if cur.is_zero(){None}else{Some((cur-T::one())&self.mask)};Some(cur)}else{None}}}#[derive(Debug,Clone)]pub struct Combinations<T>{mask:T,cur:Option<T>}impl<T>Iterator for Combinations<T>where T:BitDpExt{type Item=T;fn next(&mut self)->Option<Self::Item>{if let Some(cur)=self.cur{if cur<self.mask{self.cur=if cur==T::zero(){None}else{let x=cur&(!cur+T::one());let y=cur+x;Some(((cur&!y)/x/(T::one()+T::one()))|y)};Some(cur)}else{None}}else{None}}}}
// 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: MultiplicativeOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::multiplicative_operation_impl::MultiplicativeOperation;#[cfg_attr(any(),rustfmt::skip)]mod multiplicative_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Div,Mul}};#[doc=" $\\times$"]pub struct MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()*y.clone()}}impl<T>Unital for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{#[inline]fn unit()->Self::T{One::one()}}impl<T>Associative for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{}impl<T>Commutative for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{}impl<T>Invertible for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>+Div<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{Self::unit().div(x.clone())}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{(x.clone()).div(y.clone())}}}
// codesnip-guard: PartialIgnoredOrd
#[cfg_attr(any(),rustfmt::skip)]pub use self::partial_ignored_ord::PartialIgnoredOrd;#[cfg_attr(any(),rustfmt::skip)]mod partial_ignored_ord{#[derive(Debug,Default,Clone,Copy)]pub struct PartialIgnoredOrd<T,U>(pub T,pub U);impl<T:Eq,U>Eq for PartialIgnoredOrd<T,U>{}impl<T,U>PartialEq for PartialIgnoredOrd<T,U>where T:PartialEq{fn eq(&self,other:&Self)->bool{self.0 .eq(&other.0)}}impl<T,U>PartialOrd for PartialIgnoredOrd<T,U>where T:PartialOrd{fn partial_cmp(&self,other:&Self)->Option<std::cmp::Ordering>{self.0 .partial_cmp(&other.0)}}impl<T,U>Ord for PartialIgnoredOrd<T,U>where T:Ord{fn cmp(&self,other:&Self)->std::cmp::Ordering{self.0 .cmp(&other.0)}}}
// codesnip-guard: TupleOperation
#[cfg_attr(any(),rustfmt::skip)]mod tuple_operation_impl{use super::*;macro_rules!impl_tuple_operation{(@impl)=>{impl Magma for(){type T=();fn operate(_x:&Self::T,_y:&Self::T)->Self::T{}}impl Unital for(){fn unit()->Self::T{}}impl Associative for(){}impl Commutative for(){}impl Idempotent for(){}impl Invertible for(){fn inverse(_x:&Self::T)->Self::T{}}};(@impl$($T:ident$i:tt)*)=>{impl<$($T:Magma),*>Magma for($($T,)*){type T=($(<$T as Magma>::T,)*);fn operate(x:&Self::T,y:&Self::T)->Self::T{($(<$T as Magma>::operate(&x.$i,&y.$i),)*)}}impl<$($T:Unital),*>Unital for($($T,)*){fn unit()->Self::T{($(<$T as Unital>::unit(),)*)}}impl<$($T:Associative),*>Associative for($($T,)*){}impl<$($T:Commutative),*>Commutative for($($T,)*){}impl<$($T:Idempotent),*>Idempotent for($($T,)*){}impl<$($T:Invertible),*>Invertible for($($T,)*){fn inverse(x:&Self::T)->Self::T{($(<$T as Invertible>::inverse(&x.$i),)*)}}};(@inner$($T:ident$i:tt)*;$U:ident$j:tt$($t:tt)*)=>{impl_tuple_operation!(@impl$($T$i)*);impl_tuple_operation!(@inner$($T$i)*$U$j;$($t)*);};(@inner$($T:ident$i:tt)*;)=>{impl_tuple_operation!(@impl$($T$i)*);};($($t:tt)*)=>{impl_tuple_operation!(@inner;$($t)*);};}impl_tuple_operation!(A 0 B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9);}
// codesnip-guard: UnionFind
#[cfg_attr(any(),rustfmt::skip)]pub use self::union_find::{MergingUnionFind,PotentializedUnionFind,UndoableUnionFind,UnionFind,UnionFindBase};#[cfg_attr(any(),rustfmt::skip)]pub mod union_find{use super::{Group,Monoid};use std::{collections::HashMap,fmt::{self,Debug},marker::PhantomData,mem::{MaybeUninit,needs_drop,swap}};pub struct UnionFindBase<U,F,M,P,H>where U:UnionStrategy,F:FindStrategy,M:UfMergeSpec,P:Monoid,H:UndoStrategy<UfCell<M::Data,P>>{cells:Vec<UfCell<M::Data,P>>,merger:M,history:H::History,_marker:PhantomData<fn()->(U,F)>}impl<U,F,M,P,H>Clone for UnionFindBase<U,F,M,P,H>where U:UnionStrategy,F:FindStrategy,M:UfMergeSpec<Data:Clone>+Clone,P:Monoid,H:UndoStrategy<UfCell<M::Data,P>,History:Clone>{fn clone(&self)->Self{Self{cells:self.cells.clone(),merger:self.merger.clone(),history:self.history.clone(),_marker:self._marker}}}impl<U,F,M,P,H>Debug for UnionFindBase<U,F,M,P,H>where U:UnionStrategy,F:FindStrategy,M:UfMergeSpec<Data:Debug>,P:Monoid<T:Debug>,H:UndoStrategy<UfCell<M::Data,P>,History:Debug>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{f.debug_struct("UnionFindBase").field("cells",&self.cells).field("history",&self.history).finish()}}pub struct UfCell<D,P>where P:Monoid{parent_or_info:i32,data:MaybeUninit<D>,potential:P::T}impl<D,P>Clone for UfCell<D,P>where D:Clone,P:Monoid{fn clone(&self)->Self{let is_root=self.is_root();let potential=if is_root{P::unit()}else{self.potential.clone()};Self{parent_or_info:self.parent_or_info,data:if is_root{MaybeUninit::new(self.data().clone())}else{MaybeUninit::uninit()},potential}}}impl<D,P>Debug for UfCell<D,P>where D:Debug,P:Monoid<T:Debug>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{if let Some(info)=self.root_info(){f.debug_tuple("Root").field(&(info,self.data())).finish()}else{f.debug_tuple("Child").field(&(self.parent().unwrap(),&self.potential)).finish()}}}impl<D,P>UfCell<D,P>where P:Monoid{fn root(info:u32,data:D)->Self{let potential=P::unit();Self{parent_or_info:!(info as i32),data:MaybeUninit::new(data),potential}}fn root_info(&self)->Option<u32>{(self.parent_or_info<0).then_some((!self.parent_or_info)as u32)}fn set_root_info(&mut self,info:u32){self.parent_or_info=!(info as i32);}fn parent(&self)->Option<usize>{(self.parent_or_info>=0).then_some(self.parent_or_info as usize)}fn set_child(&mut self,parent:usize,potential:P::T){let was_root=self.is_root();self.parent_or_info=parent as i32;if needs_drop::<D>()&&was_root{unsafe{self.data.assume_init_drop()};}self.potential=potential;}fn is_root(&self)->bool{self.parent_or_info<0}fn data(&self)->&D{unsafe{self.data.assume_init_ref()}}fn data_mut(&mut self)->&mut D{unsafe{self.data.assume_init_mut()}}}impl<D,P>Drop for UfCell<D,P>where P:Monoid{fn drop(&mut self){if needs_drop::<D>()&&self.is_root(){unsafe{self.data.assume_init_drop()};}}}pub trait FindStrategy{const CHENGE_ROOT:bool;}pub enum PathCompression{}impl FindStrategy for PathCompression{const CHENGE_ROOT:bool=true;}impl FindStrategy for(){const CHENGE_ROOT:bool=false;}pub trait UnionStrategy{fn single_info()->u32;fn check_directoin(parent:&u32,child:&u32)->bool;fn unite(parent:&u32,child:&u32)->u32;}pub enum UnionBySize{}impl UnionStrategy for UnionBySize{fn single_info()->u32{1}fn check_directoin(parent:&u32,child:&u32)->bool{parent>=child}fn unite(parent:&u32,child:&u32)->u32{parent+child}}pub enum UnionByRank{}impl UnionStrategy for UnionByRank{fn single_info()->u32{0}fn check_directoin(parent:&u32,child:&u32)->bool{parent>=child}fn unite(parent:&u32,child:&u32)->u32{parent+(parent==child)as u32}}impl UnionStrategy for(){fn single_info()->u32{0}fn check_directoin(_parent:&u32,_child:&u32)->bool{false}fn unite(_parent:&u32,_child:&u32)->u32{0}}pub trait UfMergeSpec{type Data;fn merge(&mut self,to:&mut Self::Data,from:&mut Self::Data);}#[derive(Debug,Clone)]pub struct FnMerger<T,F>{f:F,_marker:PhantomData<fn()->T>}impl<T,F>UfMergeSpec for FnMerger<T,F>where F:FnMut(&mut T,&mut T){type Data=T;fn merge(&mut self,to:&mut Self::Data,from:&mut Self::Data){(self.f)(to,from)}}impl UfMergeSpec for(){type Data=();fn merge(&mut self,_to:&mut Self::Data,_from:&mut Self::Data){}}pub trait UndoStrategy<T>{const UNDOABLE:bool;type History:Default;fn unite(history:&mut Self::History,x:usize,y:usize,cells:&[T]);fn undo_unite(history:&mut Self::History,cells:&mut[T]);}pub enum Undoable{}impl<T>UndoStrategy<T>for Undoable where T:Clone{const UNDOABLE:bool=true;type History=Vec<[(usize,T);2]>;fn unite(history:&mut Self::History,x:usize,y:usize,cells:&[T]){let cx=cells[x].clone();let cy=cells[y].clone();history.push([(x,cx),(y,cy)]);}fn undo_unite(history:&mut Self::History,cells:&mut[T]){if let Some([(x,cx),(y,cy)])=history.pop(){cells[x]=cx;cells[y]=cy;}}}impl<T>UndoStrategy<T>for(){const UNDOABLE:bool=false;type History=();fn unite(_history:&mut Self::History,_x:usize,_y:usize,_cells:&[T]){}fn undo_unite(_history:&mut Self::History,_cells:&mut[T]){}}impl<U,F,P,H>UnionFindBase<U,F,(),P,H>where U:UnionStrategy,F:FindStrategy,P:Monoid,H:UndoStrategy<UfCell<(),P>>{pub fn new(n:usize)->Self{let cells:Vec<_>=(0..n).map(|_|UfCell::root(U::single_info(),())).collect();Self{cells,merger:(),history:Default::default(),_marker:PhantomData}}pub fn push(&mut self){self.cells.push(UfCell::root(U::single_info(),()));}}impl<U,F,T,Merge,P,H>UnionFindBase<U,F,FnMerger<T,Merge>,P,H>where U:UnionStrategy,F:FindStrategy,Merge:FnMut(&mut T,&mut T),P:Monoid,H:UndoStrategy<UfCell<T,P>>{pub fn new_with_merger(n:usize,mut init:impl FnMut(usize)->T,merge:Merge)->Self{let cells:Vec<_>=(0..n).map(|i|UfCell::root(U::single_info(),init(i))).collect();Self{cells,merger:FnMerger{f:merge,_marker:PhantomData},history:Default::default(),_marker:PhantomData}}}impl<F,M,P,H>UnionFindBase<UnionBySize,F,M,P,H>where F:FindStrategy,M:UfMergeSpec,P:Monoid,H:UndoStrategy<UfCell<M::Data,P>>{pub fn size(&mut self,x:usize)->usize{let root=self.find_root(x);self.root_info(root).unwrap()as usize}}impl<U,F,M,P,H>UnionFindBase<U,F,M,P,H>where U:UnionStrategy,F:FindStrategy,M:UfMergeSpec,P:Monoid,H:UndoStrategy<UfCell<M::Data,P>>{fn root_info(&self,x:usize)->Option<u32>{self.cells[x].root_info()}fn set_root_info(&mut self,x:usize,info:u32){self.cells[x].set_root_info(info);}pub fn same(&mut self,x:usize,y:usize)->bool{self.find_root(x)==self.find_root(y)}pub fn merge_data(&mut self,x:usize)->&M::Data{let root=self.find_root(x);self.cells[root].data()}pub fn merge_data_mut(&mut self,x:usize)->&mut M::Data{let root=self.find_root(x);self.cells[root].data_mut()}pub fn roots(&self)->impl Iterator<Item=usize>+'_{(0..self.cells.len()).filter(|&x|self.cells[x].is_root())}pub fn all_group_members(&mut self)->HashMap<usize,Vec<usize>>{let mut groups_map=HashMap::new();for x in 0..self.cells.len(){let r=self.find_root(x);groups_map.entry(r).or_insert_with(Vec::new).push(x);}groups_map}pub fn find(&mut self,x:usize)->(usize,P::T){let mut current=x;let mut potential=P::unit();while let Some(parent)=self.cells[current].parent(){let current_potential=self.cells[current].potential.clone();potential=P::operate(&current_potential,&potential);if F::CHENGE_ROOT&&let Some(parent_parent)=self.cells[parent].parent(){let potential=P::operate(&self.cells[parent].potential,&current_potential);self.cells[current].set_child(parent_parent,potential);}current=parent;}(current,potential)}pub fn find_root(&mut self,x:usize)->usize{let mut current=x;while let Some(parent)=self.cells[current].parent(){if F::CHENGE_ROOT&&let Some(parent_parent)=self.cells[parent].parent(){let potential=P::operate(&self.cells[parent].potential,&self.cells[current].potential);self.cells[current].set_child(parent_parent,potential);}current=parent;}current}pub fn unite_noninv(&mut self,x:usize,y:usize,potential:P::T)->bool{let(rx,potx)=self.find(x);let ry=self.find_root(y);if rx==ry||y!=ry{return false;}H::unite(&mut self.history,rx,ry,&self.cells);{let ptr=self.cells.as_mut_ptr();let(cx,cy)=unsafe{(&mut*ptr.add(rx),&mut*ptr.add(ry))};self.merger.merge(cx.data_mut(),cy.data_mut());}let info=U::unite(&self.root_info(rx).unwrap(),&self.root_info(ry).unwrap());self.set_root_info(rx,info);self.cells[ry].set_child(rx,P::operate(&potx,&potential));true}}impl<U,F,M,P,H>UnionFindBase<U,F,M,P,H>where U:UnionStrategy,F:FindStrategy,M:UfMergeSpec,P:Group,H:UndoStrategy<UfCell<M::Data,P>>{pub fn difference(&mut self,x:usize,y:usize)->Option<P::T>{let(rx,potx)=self.find(x);let(ry,poty)=self.find(y);if rx==ry{Some(P::operate(&P::inverse(&potx),&poty))}else{None}}pub fn unite_with(&mut self,x:usize,y:usize,potential:P::T)->bool{let(mut rx,potx)=self.find(x);let(mut ry,poty)=self.find(y);if rx==ry{return false;}let mut xinfo=self.root_info(rx).unwrap();let mut yinfo=self.root_info(ry).unwrap();let inverse=!U::check_directoin(&xinfo,&yinfo);let potential=if inverse{P::rinv_operate(&poty,&P::operate(&potx,&potential))}else{P::operate(&potx,&P::rinv_operate(&potential,&poty))};if inverse{swap(&mut rx,&mut ry);swap(&mut xinfo,&mut yinfo);}H::unite(&mut self.history,rx,ry,&self.cells);{let ptr=self.cells.as_mut_ptr();let(cx,cy)=unsafe{(&mut*ptr.add(rx),&mut*ptr.add(ry))};self.merger.merge(cx.data_mut(),cy.data_mut());}self.set_root_info(rx,U::unite(&xinfo,&yinfo));self.cells[ry].set_child(rx,potential);true}pub fn unite(&mut self,x:usize,y:usize)->bool{self.unite_with(x,y,P::unit())}}impl<U,M,P,H>UnionFindBase<U,(),M,P,H>where U:UnionStrategy,M:UfMergeSpec,P:Monoid,H:UndoStrategy<UfCell<M::Data,P>>{pub fn undo(&mut self){H::undo_unite(&mut self.history,&mut self.cells);}}pub type UnionFind=UnionFindBase<UnionBySize,PathCompression,(),(),()>;pub type MergingUnionFind<T,M>=UnionFindBase<UnionBySize,PathCompression,FnMerger<T,M>,(),()>;pub type PotentializedUnionFind<P>=UnionFindBase<UnionBySize,PathCompression,(),P,()>;pub type UndoableUnionFind=UnionFindBase<UnionBySize,(),(),(),Undoable>;}
// 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: bounded
#[cfg_attr(any(),rustfmt::skip)]pub use self::bounded::Bounded;#[cfg_attr(any(),rustfmt::skip)]mod bounded{#[doc=" Trait for max/min bounds"]pub trait Bounded:Sized+PartialOrd{fn maximum()->Self;fn minimum()->Self;fn is_maximum(&self)->bool{self==&Self::maximum()}fn is_minimum(&self)->bool{self==&Self::minimum()}fn set_maximum(&mut self){*self=Self::maximum()}fn set_minimum(&mut self){*self=Self::minimum()}}macro_rules!impl_bounded_num{($($t:ident)*)=>{$(impl Bounded for$t{fn maximum()->Self{$t::MAX}fn minimum()->Self{$t::MIN}})*};}impl_bounded_num!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize f32 f64);macro_rules!impl_bounded_tuple{(@impl$($T:ident)*)=>{impl<$($T:Bounded),*>Bounded for($($T,)*){fn maximum()->Self{($(<$T as Bounded>::maximum(),)*)}fn minimum()->Self{($(<$T as Bounded>::minimum(),)*)}}};(@inner$($T:ident)*,)=>{impl_bounded_tuple!(@impl$($T)*);};(@inner$($T:ident)*,$U:ident$($Rest:ident)*)=>{impl_bounded_tuple!(@impl$($T)*);impl_bounded_tuple!(@inner$($T)*$U,$($Rest)*);};($T:ident$($Rest:ident)*)=>{impl_bounded_tuple!(@inner$T,$($Rest)*);};}impl_bounded_tuple!(A B C D E F G H I J);impl Bounded for(){fn maximum()->Self{}fn minimum()->Self{}}impl Bounded for bool{fn maximum()->Self{true}fn minimum()->Self{false}}impl<T>Bounded for Option<T>where T:Bounded{fn maximum()->Self{Some(<T as Bounded>::maximum())}fn minimum()->Self{None}}impl<T>Bounded for std::cmp::Reverse<T>where T:Bounded{fn maximum()->Self{std::cmp::Reverse(<T as Bounded>::minimum())}fn minimum()->Self{std::cmp::Reverse(<T as Bounded>::maximum())}}}
// codesnip-guard: ring
#[cfg_attr(any(),rustfmt::skip)]pub use self::ring::*;#[cfg_attr(any(),rustfmt::skip)]mod ring{use super::*;use std::{marker::PhantomData,num::Wrapping,ops::{Add,Mul}};pub trait SemiRing{type T:Clone;type Additive:AbelianMonoid<T=Self::T>;type Multiplicative:Monoid<T=Self::T>;#[doc=" additive identity: $0$"]fn zero()->Self::T{<Self::Additive as Unital>::unit()}fn is_zero(x:&Self::T)->bool where Self::T:PartialEq{*x==Self::zero()}#[doc=" multiplicative identity: $1$"]fn one()->Self::T{<Self::Multiplicative as Unital>::unit()}fn is_one(x:&Self::T)->bool where Self::T:PartialEq{*x==Self::one()}#[doc=" additive operaion: $+$"]fn add(x:&Self::T,y:&Self::T)->Self::T{<Self::Additive as Magma>::operate(x,y)}#[doc=" multiplicative operaion: $+$"]fn mul(x:&Self::T,y:&Self::T)->Self::T{<Self::Multiplicative as Magma>::operate(x,y)}fn try_matrix_product(_a:&[Vec<Self::T>],_b:&[Vec<Self::T>])->Option<Vec<Vec<Self::T>>>{None}fn dot_product(x:&[Self::T],y:&[Self::T])->Self::T{assert_eq!(x.len(),y.len());x.iter().zip(y).fold(Self::zero(),|mut sum,(x,y)|{Self::add_assign(&mut sum,&Self::mul(x,y));sum})}fn add_scaled_assign(x:&mut[Self::T],y:&[Self::T],a:&Self::T){assert_eq!(x.len(),y.len());for(x,y)in x.iter_mut().zip(y){Self::add_assign(x,&Self::mul(a,y));}}fn add_assign(x:&mut Self::T,y:&Self::T){<Self::Additive as Magma>::operate_assign(x,y);}fn mul_assign(x:&mut Self::T,y:&Self::T){<Self::Multiplicative as Magma>::operate_assign(x,y);}}pub trait Ring:SemiRing<Additive:Invertible>{#[doc=" additive inverse: $-$"]fn neg(x:&Self::T)->Self::T{<Self::Additive as Invertible>::inverse(x)}#[doc=" additive right inversed operaion: $-$"]fn sub(x:&Self::T,y:&Self::T)->Self::T{<Self::Additive as Invertible>::rinv_operate(x,y)}fn sub_assign(x:&mut Self::T,y:&Self::T){<Self::Additive as Invertible>::rinv_operate_assign(x,y);}}impl<R>Ring for R where R:SemiRing<Additive:Invertible>{}pub trait Field:Ring<Multiplicative:Invertible>{#[doc=" multiplicative inverse: $-$"]fn inv(x:&Self::T)->Self::T{<Self::Multiplicative as Invertible>::inverse(x)}#[doc=" multiplicative right inversed operaion: $-$"]fn div(x:&Self::T,y:&Self::T)->Self::T{<Self::Multiplicative as Invertible>::rinv_operate(x,y)}fn div_assign(x:&mut Self::T,y:&Self::T){<Self::Multiplicative as Invertible>::rinv_operate_assign(x,y);}}impl<F>Field for F where F:Ring<Multiplicative:Invertible>{}pub trait DotProduct:Sized+Clone+Zero+Add<Output=Self>+Mul<Output=Self>{fn try_matrix_product(_a:&[Vec<Self>],_b:&[Vec<Self>])->Option<Vec<Vec<Self>>>{None}fn add_scaled_assign(x:&mut[Self],y:&[Self],a:&Self){assert_eq!(x.len(),y.len());for(x,y)in x.iter_mut().zip(y){*x=x.clone()+a.clone()*y.clone();}}fn dot_product(x:&[Self],y:&[Self])->Self{assert_eq!(x.len(),y.len());x.iter().zip(y).fold(Self::zero(),|sum,(x,y)|sum+x.clone()*y.clone())}}macro_rules!impl_dot_product{($($t:ty)*)=>{$(impl DotProduct for$t{})*};}impl_dot_product!(u8 u16 u32 u64 usize u128 i8 i16 i32 i64 isize i128 f32 f64);impl<T>DotProduct for Wrapping<T>where Wrapping<T>:Clone+Zero+Add<Output=Wrapping<T>>+Mul<Output=Wrapping<T>>{}#[doc=" $+,\\times$"]pub struct AddMulOperation<T>where T:DotProduct+One{_marker:PhantomData<fn()->T>}impl<T>SemiRing for AddMulOperation<T>where T:DotProduct+One{type T=T;type Additive=AdditiveOperation<T>;type Multiplicative=MultiplicativeOperation<T>;#[inline]fn try_matrix_product(a:&[Vec<T>],b:&[Vec<T>])->Option<Vec<Vec<T>>>{T::try_matrix_product(a,b)}#[inline]fn dot_product(x:&[Self::T],y:&[Self::T])->Self::T{T::dot_product(x,y)}#[inline]fn add_scaled_assign(x:&mut[Self::T],y:&[Self::T],a:&Self::T){T::add_scaled_assign(x,y,a);}}}
// codesnip-guard: shortest_path
#[cfg_attr(any(),rustfmt::skip)]pub use self::shortest_path::{ShortestPathExt,ShortestPathSemiRing};#[cfg_attr(any(),rustfmt::skip)]pub mod shortest_path{use super::*;use std::{cmp::{Ordering,Reverse},collections::{BinaryHeap,VecDeque},marker::PhantomData,ops::Add};pub trait ShortestPathSemiRing{type T:Clone+Ord;fn source()->Self::T;fn inf()->Self::T;fn mul(x:&Self::T,y:&Self::T)->Self::T;fn add_assign(x:&mut Self::T,y:&Self::T)->bool;}pub struct StandardSp<M>(PhantomData<fn()->M>);impl<M>ShortestPathSemiRing for StandardSp<M>where M:Monoid<T:Bounded+Ord>{type T=M::T;#[inline]fn source()->Self::T{M::unit()}#[inline]fn inf()->Self::T{M::T::maximum()}#[inline]fn mul(x:&Self::T,y:&Self::T)->Self::T{M::operate(x,y)}#[inline]fn add_assign(x:&mut Self::T,y:&Self::T)->bool{if&*x>y{*x=y.clone();true}else{false}}}pub struct OptionSp<M>(PhantomData<fn()->M>);impl<M>ShortestPathSemiRing for OptionSp<M>where M:Monoid<T:Ord>{type T=Option<M::T>;#[inline]fn source()->Self::T{Some(M::unit())}#[inline]fn inf()->Self::T{None}#[inline]fn mul(x:&Self::T,y:&Self::T)->Self::T{match(x,y){(Some(x),Some(y))=>Some(M::operate(x,y)),_=>None,}}#[inline]fn add_assign(x:&mut Self::T,y:&Self::T)->bool{if let Some(y)=y{if let Some(x)=x{if&*x>y{*x=y.clone();true}else{false}}else{*x=Some(y.clone());true}}else{false}}}pub struct PathFoldingSp<M,S>(PhantomData<fn()->(M,S)>);impl<M,S>ShortestPathSemiRing for PathFoldingSp<M,S>where M:Monoid<T:Bounded+Ord>,S:SemiRing{type T=PartialIgnoredOrd<M::T,S::T>;#[inline]fn source()->Self::T{PartialIgnoredOrd(M::unit(),S::one())}#[inline]fn inf()->Self::T{PartialIgnoredOrd(M::T::maximum(),S::zero())}#[inline]fn mul(x:&Self::T,y:&Self::T)->Self::T{PartialIgnoredOrd(M::operate(&x.0,&y.0),S::mul(&x.1,&y.1))}#[inline]fn add_assign(x:&mut Self::T,y:&Self::T)->bool{match x.0 .cmp(&y.0){Ordering::Equal=>{x.1=S::add(&x.1,&y.1);false}Ordering::Greater=>{*x=y.clone();true}_=>false,}}}pub trait ParentPolicy<G>where G:Graph{type State;fn init(graph:&G)->Self::State;fn save_parent(graph:&G,state:&mut Self::State,from:G::Vertex,to:G::Vertex);}pub enum NoParent{}impl<G>ParentPolicy<G>for NoParent where G:Graph{type State=();fn init(_graph:&G){}fn save_parent(_graph:&G,_state:&mut Self::State,_from:G::Vertex,_to:G::Vertex){}}pub struct RecordParent;impl<G>ParentPolicy<G>for RecordParent where G:Graph+VertexMap<Option<<G as Graph>::Vertex>>{type State=<G as VertexMap<Option<<G as Graph>::Vertex>>>::Vmap;fn init(graph:&G)->Self::State{graph.construct_vmap(| |None)}fn save_parent(graph:&G,state:&mut Self::State,from:G::Vertex,to:G::Vertex){*graph.vmap_get_mut(state,to)=Some(from);}}pub struct ShortestPathWithParent<G,S,P=RecordParent>where G:Graph+VertexMap<S::T>,S:ShortestPathSemiRing,P:ParentPolicy<G>{pub dist:<G as VertexMap<S::T>>::Vmap,pub parent:P::State}impl<G,S>ShortestPathWithParent<G,S,RecordParent>where G:Graph+VertexMap<S::T>+VertexMap<Option<<G as Graph>::Vertex>>,S:ShortestPathSemiRing{pub fn path_to(&self,graph:&G,target:G::Vertex)->Option<Vec<G::Vertex>>{let dist:&S::T=graph.vmap_get(&self.dist,target);if dist==&S::inf(){return None;}let mut cur=target;let mut path=vec![cur];while let&Some(p)=graph.vmap_get(&self.parent,cur){path.push(p);cur=p;}path.reverse();Some(path)}}pub trait ShortestPathExt:Graph{fn standard_sp<'a,M>(&'a self)->ShortestPathBuilder<'a,Self,StandardSp<M>>where Self:Sized,M:Monoid<T:Bounded+Ord>{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn standard_sp_additive<'a,T>(&'a self)->ShortestPathBuilder<'a,Self,StandardSp<AdditiveOperation<T>>>where Self:Sized,T:Clone+Zero+Add<Output=T>+Bounded+Ord{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn option_sp<'a,M>(&'a self)->ShortestPathBuilder<'a,Self,OptionSp<M>>where Self:Sized,M:Monoid<T:Ord>{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn option_sp_additive<'a,T>(&'a self)->ShortestPathBuilder<'a,Self,OptionSp<AdditiveOperation<T>>>where Self:Sized,T:Clone+Zero+Add<Output=T>+Ord{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn path_folding_sp<'a,M,S>(&'a self)->ShortestPathBuilder<'a,Self,PathFoldingSp<M,S>>where Self:Sized,M:Monoid<T:Bounded+Ord>,S:SemiRing{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn path_folding_sp_additive_addmul<'a,T,U>(&'a self)->ShortestPathBuilder<'a,Self,PathFoldingSp<AdditiveOperation<T>,AddMulOperation<U>>>where Self:Sized,T:Clone+Zero+Add<Output=T>+Bounded+Ord,U:DotProduct+One{ShortestPathBuilder{graph:self,_marker:PhantomData}}}impl<G>ShortestPathExt for G where G:Graph+?Sized{}pub struct ShortestPathBuilder<'a,G,S,P=NoParent>where G:Graph,S:ShortestPathSemiRing,P:ParentPolicy<G>{graph:&'a G,_marker:PhantomData<fn()->(S,P)>}impl<'a,G,S,P>ShortestPathBuilder<'a,G,S,P>where G:Graph,S:ShortestPathSemiRing,P:ParentPolicy<G>{fn bfs_distance_core<M,I>(&self,sources:I,weight:&M)->ShortestPathWithParent<G,S,P>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T+?Sized,I:IntoIterator<Item=G::Vertex>{let graph=self.graph;let mut dist=graph.construct_vmap(S::inf);let mut parent=P::init(graph);let mut deq=VecDeque::new();for source in sources.into_iter(){*graph.vmap_get_mut(&mut dist,source)=S::source();deq.push_back(source);}let zero=S::source();while let Some(u)=deq.pop_front(){for neighbor in graph.neighbors(u){let v=neighbor.to;let w=weight(neighbor.label);let nd=S::mul(graph.vmap_get(&dist,u),&w);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){P::save_parent(graph,&mut parent,u,v);if w==zero{deq.push_front(v);}else{deq.push_back(v);}}}}ShortestPathWithParent{dist,parent}}fn dijkstra_core<M,I>(&self,sources:I,weight:&M,mut stop:impl FnMut(G::Vertex)->bool)->ShortestPathWithParent<G,S,P>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T+?Sized,I:IntoIterator<Item=G::Vertex>{let graph=self.graph;let mut dist=graph.construct_vmap(S::inf);let mut parent=P::init(graph);let mut heap=BinaryHeap::new();for source in sources.into_iter(){*graph.vmap_get_mut(&mut dist,source)=S::source();heap.push(PartialIgnoredOrd(Reverse(S::source()),source));}while let Some(PartialIgnoredOrd(Reverse(d),u))=heap.pop(){let current=graph.vmap_get(&dist,u);if current!=&d{continue;}if stop(u){break;}let d=current.clone();for neighbor in graph.neighbors(u){let v=neighbor.to;let weight=weight(neighbor.label);let nd=S::mul(&d,&weight);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){P::save_parent(graph,&mut parent,u,v);heap.push(PartialIgnoredOrd(Reverse(nd),v));}}}ShortestPathWithParent{dist,parent}}fn bellman_ford_core<M,I>(&self,sources:I,weight:&M,check:bool)->Option<ShortestPathWithParent<G,S,P>>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T+?Sized,I:IntoIterator<Item=G::Vertex>,P:ParentPolicy<G>{let graph=self.graph;let mut dist=graph.construct_vmap(S::inf);let mut parent=P::init(graph);for source in sources.into_iter(){*graph.vmap_get_mut(&mut dist,source)=S::source();}let vsize=graph.vsize();for _ in 1..vsize{let mut updated=false;for u in graph.vertices(){for neighbor in graph.neighbors(u){let v=neighbor.to;let weight=weight(neighbor.label);let nd=S::mul(graph.vmap_get(&dist,u),&weight);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){P::save_parent(graph,&mut parent,u,v);updated=true;}}}if!updated{break;}}if check{for u in graph.vertices(){for neighbor in graph.neighbors(u){let v=neighbor.to;let weight=weight(neighbor.label);let nd=S::mul(graph.vmap_get(&dist,u),&weight);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){return None;}}}}Some(ShortestPathWithParent{dist,parent})}}impl<'a,G,S>ShortestPathBuilder<'a,G,S,NoParent>where G:Graph,S:ShortestPathSemiRing{pub fn with_parent(self)->ShortestPathBuilder<'a,G,S,RecordParent>where G:VertexMap<Option<<G as Graph>::Vertex>>{ShortestPathBuilder{graph:self.graph,_marker:PhantomData}}pub fn bfs_distance<M,I>(&self,sources:I,weight:M)-><G as VertexMap<S::T>>::Vmap where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bfs_distance_core(sources,&weight).dist}pub fn dijkstra<M,I>(&self,sources:I,weight:M)-><G as VertexMap<S::T>>::Vmap where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.dijkstra_core(sources,&weight,|_|false).dist}pub fn bellman_ford<M,I>(&self,sources:I,weight:M,check:bool)->Option<<G as VertexMap<S::T>>::Vmap>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bellman_ford_core(sources,&weight,check).map(|sp|sp.dist)}pub fn warshall_floyd_ap<M>(&self,weight:M)-><G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap where G:VertexMap<S::T,Vmap:Clone>+VertexMap<<G as VertexMap<S::T>>::Vmap>,M:Fn(G::Label)->S::T{let graph=self.graph;let mut dist=graph.construct_vmap(| |graph.construct_vmap(S::inf));for u in graph.vertices(){*graph.vmap_get_mut(graph.vmap_get_mut(&mut dist,u),u)=S::source();}for u in graph.vertices(){for neighbor in graph.neighbors(u){let weight=weight(neighbor.label);S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist,u),neighbor.to),&weight);}}for k in graph.vertices(){for i in graph.vertices(){for j in graph.vertices(){let d1=graph.vmap_get(graph.vmap_get(&dist,i),k);let d2=graph.vmap_get(graph.vmap_get(&dist,k),j);let nd=S::mul(d1,d2);S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist,i),j),&nd);}}}dist}}impl<'a,G,S>ShortestPathBuilder<'a,G,S,RecordParent>where G:Graph+VertexMap<Option<<G as Graph>::Vertex>>,S:ShortestPathSemiRing{pub fn bfs_distance<M,I>(&self,sources:I,weight:M)->ShortestPathWithParent<G,S>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bfs_distance_core(sources,&weight)}pub fn dijkstra<M,I>(&self,sources:I,weight:M)->ShortestPathWithParent<G,S>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.dijkstra_core(sources,&weight,|_|false)}pub fn bellman_ford<M,I>(&self,sources:I,weight:M,check:bool)->Option<ShortestPathWithParent<G,S>>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bellman_ford_core(sources,&weight,check)}}impl<'a,G,M,P>ShortestPathBuilder<'a,G,StandardSp<M>,P>where G:Graph,M:Monoid<T:Bounded+Ord>,P:ParentPolicy<G>{#[doc=" Distances other than the target may remain tentative."]pub fn dijkstra_to<W,I>(&self,sources:I,target:G::Vertex,weight:W)->ShortestPathWithParent<G,StandardSp<M>,P>where G:VertexMap<M::T>,W:Fn(G::Label)->M::T,I:IntoIterator<Item=G::Vertex>{self.dijkstra_core(sources,&weight,|u|u==target)}}}
// 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())});}