// 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: 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: 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{}};}}