#![allow(dead_code)]

pub use __cargo_equip::prelude::*;

use minimal_lib_graph::{dijkstra, Graph};
fn main() {
    proconio::input! {
        n: usize,
        m: usize,
    }
    let mut g = Graph::new_with_node(n);
    for _ in 0..m {
        proconio::input! {
            k: usize,
            c: i64,
            xs: [i64; k],
        }
        let hub_odd = g.add_node(0);
        let hub_even = g.add_node(0);
        for i in 0..k {
            let xi = (xs[i] - 1) as usize;
            if xs[i] & 1 > 0 {
                g.add_edge(xi, hub_odd, c + xs[i]);
                g.add_edge(hub_odd, xi, c + xs[i]);
                g.add_edge(hub_even, xi, c + xs[i] + 1);
            } else {
                g.add_edge(xi, hub_even, c + xs[i]);
                g.add_edge(hub_odd, xi, c + xs[i] + 1);
                g.add_edge(hub_even, xi, c + xs[i]);
            }
        }
    }
    println!(
        "{}",
        dijkstra(&g, 0, Some(n - 1), |e| (*e as u64))[n - 1]
            .map(|x| (x / 2) as i64)
            .unwrap_or(-1)
    );
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`                          licensed under `MIT/Apache-2.0`    as `crate::__cargo_equip::crates::lazy_static`
///  - `minimal-lib-algo 0.1.0 (path+██████████████████████████████████)`          published in **missing** licensed under **missing**         as `crate::__cargo_equip::crates::__minimal_lib_algo_0_1_0`
///  - `minimal-lib-graph 0.1.0 (path+███████████████████████████████████)`        published in **missing** licensed under **missing**         as `crate::__cargo_equip::crates::minimal_lib_graph`
///  - `proconio 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)`                             licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
/// 
///  # Procedural macros
/// 
///  - `proconio-derive 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
/// 
///  # License and Copyright Notices
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      Copyright (c) 2010 The Rust Project Developers
/// 
///      Permission is hereby granted, free of charge, to any
///      person obtaining a copy of this software and associated
///      documentation files (the "Software"), to deal in the
///      Software without restriction, including without
///      limitation the rights to use, copy, modify, merge,
///      publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software
///      is furnished to do so, subject to the following
///      conditions:
/// 
///      The above copyright notice and this permission notice
///      shall be included in all copies or substantial portions
///      of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
///      ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
///      TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
///      PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
///      SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
///      CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
///      OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
///      IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
///      DEALINGS IN THE SOFTWARE.
///      ```
/// 
///  - `proconio 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      The MIT License
///      Copyright 2019 (C) statiolake <statiolake@gmail.com>
/// 
///      Permission is hereby granted, free of charge, to any person obtaining a copy of
///      this software and associated documentation files (the "Software"), to deal in
///      the Software without restriction, including without limitation the rights to
///      use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software is furnished to do so,
///      subject to the following conditions:
/// 
///      The above copyright notice and this permission notice shall be included in all
///      copies or substantial portions of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
///      IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
///      FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
///      COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
///      IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
///      CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
/// 
///      Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019.  The
///      original macro is licensed under BSD 3-clause license.
/// 
///      Redistribution and use in source and binary forms, with or without
///      modification, are permitted provided that the following conditions are met:
/// 
///      1. Redistributions of source code must retain the above copyright notice, this
///         list of conditions and the following disclaimer.
/// 
///      2. Redistributions in binary form must reproduce the above copyright notice,
///         this list of conditions and the following disclaimer in the documentation
///         and/or other materials provided with the distribution.
/// 
///      3. Neither the name of the copyright holder nor the names of its contributors
///         may be used to endorse or promote products derived from this software
///         without specific prior written permission.
/// 
///      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
///      ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
///      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
///      DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
///      FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
///      DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
///      SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
///      CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
///      OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
///      OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///      ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod lazy_static {#![no_std]use crate::__cargo_equip::preludes::lazy_static::*;pub use crate::__cargo_equip::macros::lazy_static::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::lazy_static::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T>{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T>{}#[macro_export]macro_rules!__cargo_equip_macro_def_lazy_static___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::lazy_static::lazy::Lazy<$T> =$crate::__cargo_equip::crates::lazy_static::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_lazy_static___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_lazy_static___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::lazy_static::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::lazy_static::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_lazy_static___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_lazy_static_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_lazy_static_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
        pub mod __minimal_lib_algo_0_1_0 {pub mod bisect{pub fn bisect_predicate_max(f:impl Fn(i64)->bool,l:i64,r:i64)->Option<i64>{let one=1;let two=one+one;let mut unchanged=true;let mut l=l;let mut r=r+one;while(l+one)<r{let h=(l+r)/two;if f(h){unchanged=false;l=h;}else{r=h;}}if unchanged&&!f(l){return None;}Some(l)}pub fn bisect_predicate_min(f:impl Fn(i64)->bool,l:i64,r:i64)->Option<i64>{let one=1;let two=one+one;let mut unchanged=true;let mut l=l;let mut r=r;if!f(r){return None;}while(l+one)<r{let h=(l+r)/two;if f(h){r=h;}else{unchanged=false;l=h;}}if unchanged&&f(l){return Some(l);}Some(r)}}pub mod compress{use std::{collections::{BTreeMap,HashMap},hash::Hash,};pub struct Compress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:HashMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>Compress<T>{pub fn new<'a>(it:&[T])->Compress<T>{let mut count=0;let mut last=None;let mut to_index=HashMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}#[derive(Debug)]pub struct SegmentCompress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:BTreeMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>SegmentCompress<T>{pub fn new<'a>(it:&[T])->Self{let mut count=0;let mut last=None;let mut to_index=BTreeMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{last=Some(y);continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn get_range(&self,left:T,right:T)->Option<(usize,usize)>{let mut rn=self.to_index.range(left.clone()..right.clone());let mut rn2=self.to_index.range(left..right);Some((*rn.next()?.1,*rn2.next_back()?.1))}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}}pub mod runlength{pub fn runlength<T>(xs:&[T])->Vec<(T,usize)>where T:Eq+Clone,{let mut result=vec![];let mut run=1;let mut prev_index=0;for(index,item)in xs.iter().enumerate().skip(1){if item==&xs[prev_index]{run+=1;}else{result.push((xs[prev_index].clone(),run));prev_index=index;run=1;}}result.push((xs[prev_index].clone(),run));result}}pub mod uf{pub struct UnionFind{vec:Vec<usize>,component_size:Vec<usize>,}impl UnionFind{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push(i);component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->usize{let mut a=a;let mut stack=Vec::new();loop{let parent=self.vec[a];if parent==a{for i in stack{self.vec[i]=a;}return a;}else{stack.push(a);a=parent;}}}pub fn union(&mut self,a:usize,b:usize){let a_root=self.find_root(a);let b_root=self.find_root(b);if a_root!=b_root{self.vec[a_root]=b_root;self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->bool{self.find_root(a)==self.find_root(b)}}}pub mod monotone_minima{pub struct MonotoneMinima<'a,T:Ord>{rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>}impl<'a,T:Ord>MonotoneMinima<'a,T>{pub fn new(rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>)->Self{Self{rows,columns,func}}fn minima_recur(&self,result:&mut[usize],yl:usize,yr:usize,xl:usize,xr:usize){if yl==yr{return;}let mid=(yl+yr)/2;let mut pos=xl;let mut minimum_value=(self.func)(mid,xl);for i in(xl+1)..xr{let v=(self.func)(mid,i);if v<minimum_value{minimum_value=v;pos=i;}}result[mid]=pos;self.minima_recur(result,yl,mid,xl,pos+1,);self.minima_recur(result,mid+1,yr,pos,xr,);}pub fn minimas(&self)->Vec<usize>{let mut result=vec![0;self.rows];self.minima_recur(&mut result,0,self.rows,0,self.columns);result}}}pub mod interval_set{use std::collections::BTreeMap;#[derive(Debug,Clone)]pub struct IntervalSet<T>where T:Ord+Copy{s:BTreeMap<T,T>,}impl<T>IntervalSet<T>where T:Ord+Copy{pub fn new()->Self{Self{s:BTreeMap::new()}}pub fn get(&self,x:T)->Option<(T,T)>{use std::ops::Bound::*;self.s.range((Unbounded,Included(x))).next_back().filter(|&(_l,r)|x<*r).map(|(x,y)|(*x,*y))}pub fn insert(&mut self,l:T,r:T){use std::ops::Bound::*;let(l,r)=if let Some((il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<=*ir{if*ir<r{*ir=r;}(*il,*ir)}else{self.s.insert(l,r);(l,r)}}else{self.s.insert(l,r);(l,r)};while let Some((il,ir))=self.s.range((Unbounded,Included(r))).next_back(){let il=*il;let ir=*ir;if l==il{break;}let cur_seg_r=self.s.get_mut(&l).unwrap();if r<ir{*cur_seg_r=ir;}self.s.remove(&il);}}pub fn remove(&mut self,l:T,r:T){use std::ops::Bound::*;if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let t=*ir;*ir=l;self.s.insert(r,t);}else if l<*ir{*ir=l;}};while let Some((il,ir))=self.s.range((Included(l),Excluded(r))).next(){let il=*il;let ir=*ir;let cur_seg_r=self.s.get_mut(&il).unwrap();if l<ir{*cur_seg_r=r;}self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<*ir{*ir=l;}};}pub fn intervals(&self)->Vec<(T,T)>{self.s.iter().map(|(x,y)|(*x,*y)).collect()}pub fn intersect(&mut self,l:T,r:T){use std::ops::Bound::*;while let Some((il,ir))=self.s.range((Unbounded,Excluded(l))).next(){let il=*il;let ir=*ir;self.s.remove(&il);if l<ir{self.s.insert(l,ir);}}while let Some((il,_ir))=self.s.range((Included(r),Unbounded)).next(){let il=*il;self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let t=*ir;*ir=r;}};}pub fn append(&mut self,new:&Self){for(l,r)in new.intervals().into_iter(){self.insert(l,r);}}}}}
        pub mod minimal_lib_graph {use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub mod abstract_graph{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use crate::__cargo_equip::crates::minimal_lib_graph::{graph::{EdgeId,NodeId},Edge,Graph,Vertex,};pub trait AbstractGraph<V,E>{fn n_nodes(&self)->usize;fn n_edges(&self)->usize;fn get_node(&self,node:usize)->&Vertex<V>;fn get_edge(&self,edge:usize)->&Edge<E>;fn get_outgoing_edges(&self,node:usize)->Vec<&Edge<E>>;fn get_incoming_edges(&self,node:usize)->Vec<&Edge<E>>;}impl<V,E>AbstractGraph<V,E>for Graph<V,E>{fn n_nodes(&self)->usize{self.vs.len()}fn n_edges(&self)->usize{self.es.len()}fn get_node(&self,node:NodeId)->&Vertex<V>{Graph::get_node(self,node)}fn get_edge(&self,edge:EdgeId)->&Edge<E>{Graph::get_edge(self,edge)}fn get_outgoing_edges(&self,node:NodeId)->Vec<&Edge<E>>{Graph::get_outgoing_edges(self,node)}fn get_incoming_edges(&self,node:NodeId)->Vec<&Edge<E>>{Graph::get_incoming_edges(self,node)}}}pub mod algo{use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub mod cc{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::HashMap;use crate::__cargo_equip::crates::minimal_lib_graph::{abstract_graph::AbstractGraph,uf::UnionFind,Graph};pub fn connected_components<V,E>(g:&Graph<V,E>)->Vec<Vec<usize>>{let vn=g.n_nodes();let mut uf=UnionFind::new(vn);let mut bcc=HashMap::new();for e in g.es.iter(){uf.union(e.source,e.dest);}for i in 0..vn{let r=uf.find_root(i);bcc.entry(r).or_insert_with(Vec::new).push(i);}bcc.into_iter().map(|x|x.1).collect()}}pub mod cycle{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use crate::__cargo_equip::crates::minimal_lib_graph::{visit::DfsAll,Graph};pub fn detect_cycle<V,E>(g:&Graph<V,E>)->Option<Vec<usize>>{let dfs=DfsAll::new(g);let vn=g.vs.len();let mut e_in=vec![None;vn];let mut visiting=vec![false;vn];for(_,node)in dfs.enumerate(){match node{crate::__cargo_equip::crates::minimal_lib_graph::visit::dfs_all::Order::Pre{node,from_edge,..}=>{e_in[node]=from_edge;visiting[node]=true;for e in g.get_outgoing_edges(node){if from_edge.is_some()&&Some(e.index)!=from_edge{let other_side=e.other_side(node);if visiting[other_side]{let mut n=node;let mut res=Vec::new();while n!=other_side{let from_ei=e_in[n].unwrap();let fe=g.get_edge(from_ei);res.push(from_ei);n=fe.other_side(n);}res.reverse();res.push(e.index);return Some(res);}}}}crate::__cargo_equip::crates::minimal_lib_graph::visit::dfs_all::Order::Post{node,..}=>{visiting[node]=false;}}}None}}pub mod dijkstra{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::{cmp::Reverse,collections::{BinaryHeap,VecDeque},};use crate::__cargo_equip::crates::minimal_lib_graph::graph::Graph;pub fn dijkstra<V,E>(g:&Graph<V,E>,start:usize,goal:Option<usize>,weight_fn:impl Fn(&E)->u64,)->Vec<Option<u64>>{let mut distance:Vec<Option<u64>> =vec![None;g.vs.len()];let mut visited:Vec<bool> =vec![false;g.vs.len()];let mut queue=BinaryHeap::new();queue.push(Reverse((0,start)));while let Some(Reverse((dist,node)))=queue.pop(){if!visited[node]{distance[node]=Some(dist);visited[node]=true;if goal==Some(node){break;}for e in g.get_outgoing_edges(node).into_iter(){let ew=weight_fn(&e.value);let dest=e.other_side(node);if!visited[dest]{match distance.get_mut(dest).unwrap(){Some(cur_dist)=>{if dist+ew<*cur_dist{*cur_dist=dist+ew;queue.push(Reverse((dist+ew,dest)));}}None=>{distance[dest]=Some(dist+ew);queue.push(Reverse((dist+ew,dest)));}}}}}}distance}pub fn path_reform<V,E>(g:&Graph<V,E>,start:usize,goal:usize,weight_fn:impl Fn(&E)->u64,potential:&[Option<u64>],)->Vec<usize>{let mut node=goal;let mut visited:Vec<bool> =vec![false;g.vs.len()];let mut v=VecDeque::with_capacity(g.vs.len());while node!=start{let np=potential[node].unwrap();visited[node]=true;for i in g.get_incoming_edges(node){let source=i.other_side(node);if!visited[source]{if let Some(p)=potential[source]{if p+weight_fn(&i.value)<=np{v.push_front(node);node=source;break;}}}}}v.push_front(start);v.into()}}pub mod dinic{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::{cell::RefCell,collections::VecDeque};use crate::__cargo_equip::crates::minimal_lib_graph::{abstract_graph::AbstractGraph,Graph};fn pathfinder(g:&mut Graph<i64,i64>,next_edges:&Vec<RefCell<VecDeque<usize>>>,target:usize,node:usize,bottleneck:Option<i64>,)->i64{if node==target{return bottleneck.unwrap();}let mut value=0;while let Some(e)={let mut b=next_edges[node].borrow_mut();b.pop_back()}{let edge=g.get_edge(e);let next_node=edge.dest;if edge.value==0{continue;}if bottleneck==Some(value){next_edges[node].borrow_mut().push_back(e);break;}let bottleneck=match bottleneck{Some(bottleneck)=>(bottleneck-value).min(edge.value),None=>edge.value,};let new_flow=pathfinder(g,next_edges,target,next_node,Some(bottleneck));g.get_edge_mut(e).value-=new_flow;g.get_edge_mut(e^1).value+=new_flow;value+=new_flow;}value}pub struct Flow{pub total_flow:i64,pub edge_flows:Vec<i64>,}pub fn dinic(g:&Graph<i64,i64>,start:usize,goal:usize)->Flow{let mut flow=0;let vn=g.n_nodes();let mut residual:Graph<i64,i64> =Graph::new_with_node(vn);for e in g.es.iter(){residual.add_edge(e.source,e.dest,e.value);residual.add_edge(e.dest,e.source,0);}loop{let levels={let mut visited=vec![false;vn];let mut levels=vec![None;vn];let mut visit_next=VecDeque::new();levels[start]=Some(0);visit_next.push_back((0,start));while let Some((node_score,node))=visit_next.pop_front(){if visited[node]{continue;}if goal==node{break;}for edge in residual.get_outgoing_edges(node){if edge.value<=0{continue;}let next=edge.dest;if visited[next]{continue;}let next_score=node_score+1;levels[next]=Some(next_score);visit_next.push_back((next_score,next));}visited[node]=true;}levels};let mut next_edges=vec![RefCell::new(VecDeque::new());vn];for e in&residual.es{if e.value==0{continue;}if let Some(s)=levels[e.source]{levels[e.dest].map(|d|{if s+1==d{next_edges[e.source].borrow_mut().push_back(e.index);}});}}let df=pathfinder(&mut residual,&mut next_edges,goal,start,None);flow+=df;if df==0{break;}}let en=g.n_edges();let mut edge_flows=vec![0;en];for i in 0..en{edge_flows[i]=residual.es[(i<<1)+1].value;}Flow{total_flow:flow,edge_flows,}}}pub mod lowlink{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::{HashMap,VecDeque};use crate::__cargo_equip::crates::minimal_lib_graph::uf::UnionFind;use crate::__cargo_equip::crates::minimal_lib_graph::{visit::dfs_all::DfsAll,Graph};#[derive(Debug)]pub struct LowLink{pub ord:Vec<usize>,pub low:Vec<usize>,pub bridges:Vec<usize>,pub artics:Vec<usize>,}pub fn calc_lowlink<V,E>(g:&Graph<V,E>)->LowLink{let dfs=DfsAll::new(g);let vn=g.vs.len();let mut ord=vec![None;g.vs.len()];let mut low=vec![vn;g.vs.len()];let mut n_ch=vec![0;g.vs.len()];let mut bridges=Vec::new();let mut artics=Vec::new();let mut cnt=0;for(_,node)in dfs.enumerate(){match node{crate::__cargo_equip::crates::minimal_lib_graph::visit::dfs_all::Order::Pre{node,from_edge,..}=>{ord[node]=Some(cnt);low[node]=cnt;cnt+=1;from_edge.map(|ei|{let f=g.get_edge(ei).source;n_ch[f]+=1;});}crate::__cargo_equip::crates::minimal_lib_graph::visit::dfs_all::Order::Post{node,from_edge,..}=>{let i=ord[node].unwrap();for e in g.get_incoming_edges(node){if Some(e.index)==from_edge{}else if ord[e.source]<ord[node]{low[node]=std::cmp::min(low[node],ord[e.source].unwrap());}else{low[node]=std::cmp::min(low[node],low[e.source]);}}if let Some(from_edge)=from_edge{let from_node=g.get_edge(from_edge).source;low[from_node]=std::cmp::min(low[from_node],low[node]);}let outgo=g.get_outgoing_edges(node);let mut is_artic=from_edge.is_none()&&n_ch[i]>=2;for e in outgo.into_iter(){if i<low[e.dest]{bridges.push(e.index);bridges.push(e.index^1);is_artic=true;}}if is_artic{artics.push(i);}}}}let ord=ord.into_iter().map(|x|x.unwrap()).collect();bridges.sort();artics.sort();LowLink{ord,low,bridges,artics,}}pub fn edge_2_connected_components<V,E>(g:&Graph<V,E>)->Vec<Vec<usize>>{let vn=g.vs.len();let bridges=calc_lowlink(g).bridges;let mut uf=UnionFind::new(vn);let mut bcc=HashMap::new();let mut last_index=0;let bl=bridges.len()-1;for i in 0..g.es.len(){if bridges.get(last_index)==Some(&i){if last_index<bl{last_index+=1;}}else{uf.union(g.es[i].source,g.es[i].dest);}}for i in 0..vn{let r=uf.find_root(i);bcc.entry(r).or_insert_with(Vec::new).push(i);}bcc.into_iter().map(|x|x.1).collect()}pub fn vertex_2_connected_components<V,E>(g:&Graph<V,E>)->Vec<Vec<usize>>{let dfs=DfsAll::new(g);let vn=g.vs.len();let mut ord=vec![None;g.vs.len()];let mut low=vec![vn;g.vs.len()];let mut edge_stack=VecDeque::new();let mut bcc=Vec::new();let mut cnt=0;for(_,node)in dfs.enumerate(){match node{crate::__cargo_equip::crates::minimal_lib_graph::visit::dfs_all::Order::Pre{node,from_edge,..}=>{ord[node]=Some(cnt);low[node]=cnt;cnt+=1;if let Some(from_edge)=from_edge{edge_stack.push_back(from_edge);}}crate::__cargo_equip::crates::minimal_lib_graph::visit::dfs_all::Order::Post{node,from_edge}=>{for e in g.get_incoming_edges(node){if Some(e.index)==from_edge{}else if ord[e.source]<ord[node]{low[node]=std::cmp::min(low[node],ord[e.source].unwrap());}else{low[node]=std::cmp::min(low[node],low[e.source]);}}if let Some(from_edge)=from_edge{let from_node=g.get_edge(from_edge).source;low[from_node]=std::cmp::min(low[from_node],low[node]);let from_node_ord=ord[from_node].unwrap();if from_node_ord<=low[node]{let mut bcc_item=vec![from_node];while let Some(sei)=edge_stack.pop_back(){let se=g.get_edge(sei);bcc_item.push(se.dest);if se.dest==node{break;}}bcc.push(bcc_item);}}else if g.get_outgoing_edges(node).is_empty(){bcc.push(vec![node]);}}}}bcc}}pub mod scc{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::VecDeque;use crate::__cargo_equip::crates::minimal_lib_graph::{visit::dfs_post::DfsPost,Graph};use super::toposort::toposort;pub fn decomp_scc<V,E>(g:&Graph<V,E>)->Vec<Vec<usize>>{let mut po_stack=VecDeque::new();let dfs=DfsPost::new(g);for node in dfs{po_stack.push_back(node);}let mut reduced=Graph::new();let mut res=Vec::new();let mut visited=vec![None;g.vs.len()];let mut scc_id=0;let mut stack=VecDeque::new();while let Some(node)=po_stack.pop_back(){if visited[node].is_none(){visited[node]=Some(scc_id);let mut cur_scc=vec![node];reduced.add_node(());stack.clear();stack.push_back((node,0));while let Some((node,idx))=stack.back_mut(){let v=&g.vs[*node];loop{if*idx<v.incoming.len(){if let Some(e)=v.incoming.get(*idx){let source=g.es[*e].source;if visited[source].is_none(){visited[source]=Some(scc_id);cur_scc.push(source);*idx+=1;stack.push_back((source,0));break;}else{let income_scc=visited[source].unwrap();if income_scc!=scc_id{reduced.add_edge(income_scc,scc_id,());}*idx+=1;continue;}}}else{stack.pop_back();break;}}}cur_scc.reverse();res.push(Some(cur_scc));scc_id+=1;}}let topo=toposort(&reduced).unwrap();topo.into_iter().map(|x|res[x].take().unwrap()).collect()}}pub mod toposort{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::VecDeque;use crate::__cargo_equip::crates::minimal_lib_graph::Graph;pub fn toposort<V,E>(g:&Graph<V,E>)->Option<Vec<usize>>{let vn=g.vs.len();let mut s=VecDeque::new();let mut inconming=vec![0;vn];let mut res=Vec::with_capacity(vn);for(i,v)in g.vs.iter().enumerate(){inconming[i]=v.incoming.len();if inconming[i]==0{s.push_back(i);}}while let Some(vi)=s.pop_front(){res.push(vi);for ei in g.vs[vi].outgoing.iter(){let e=&g.es[*ei];inconming[e.dest]-=1;if inconming[e.dest]==0{s.push_back(e.dest);}}}if res.len()==vn{Some(res)}else{None}}}pub mod clique{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use crate::__cargo_equip::crates::minimal_lib_graph::{abstract_graph::AbstractGraph,Graph};pub fn enumerate_clique<V,E>(g:&Graph<V,E>)->Vec<Vec<usize>>{let e=g.n_edges();let v=g.n_nodes();let mut res=Vec::new();let mut degrees=vec![];let mut connected=vec![0i128;v];let mut connected_ids=vec![vec![];v];for i in 0..v{let es=g.get_outgoing_edges(i);let degree=es.len();connected[i]|=1<<i;for ei in es{connected[i]|=1<<ei.dest;connected_ids[i].push(ei.dest);}degrees.push((degree,i));}degrees.sort();let mut visited=vec![false;v];for(_,i)in degrees.into_iter(){let conn:Vec<usize> =connected_ids[i].iter().cloned().filter(|&x|!visited[x]).collect();let d=conn.len();if d*d>2*e{continue;}visited[i]=true;for j in 0..(1<<d){let mut f=true;let mut bits=1i128<<i;for k in 0..d{if(j>>k)&1==1{bits|=1<<conn[k];}}for k in 0..d{if(j>>k)&1==1&&(bits&connected[conn[k]])<bits{f=false;break;}}if f{let mut r=vec![i];for k in 0..d{if(j>>k)&1==1{r.push(conn[k]);}}res.push(r);}}}res}}pub mod mincostflow{use crate::__cargo_equip::preludes::minimal_lib_graph::*;#[derive(Debug)]pub struct Constraint{pub min:i64,pub max:i64,pub cost:i64,}#[derive(Debug)]pub struct InternalConstraint{pub cap_left:i64,pub cost:i64,}#[derive(Debug)]pub struct Edge{src:usize,dest:usize,constraint:Constraint,}#[derive(Debug)]struct GraphState<'a>{es:&'a[Edge],vert_diff:Vec<i64>,flow:Vec<i64>,dual:Vec<i64>,}use std::{collections::{BTreeSet,HashSet},ops::BitXor,};use crate::__cargo_equip::crates::minimal_lib_graph::{abstract_graph::AbstractGraph,Graph};type Flow=Vec<i64>;type Potential=Vec<i64>;pub fn naive_mincostflow(g:&Graph<i64,Constraint>)->Result<FlowResult,InfeasibleFlowResult>{let vn=g.n_nodes();let en=g.n_edges();let mut residual:Graph<i64,InternalConstraint> =Graph::new_with_node(vn);let mut flow=vec![0;en];let mut delta=vec![0;vn];let mut cur_cost:i128=0;{for i in 0..vn{let node=&g.vs[i];delta[i]+=node.value;}}for i in 0..en{let e=&g.es[i];if e.value.cost>=0{flow[i]=e.value.min;cur_cost+=(flow[i]*e.value.cost)as i128;delta[e.source]-=e.value.min;delta[e.dest]+=e.value.min;residual.add_edge(e.source,e.dest,InternalConstraint{cap_left:e.value.max-e.value.min,cost:e.value.cost,},);residual.add_edge(e.dest,e.source,InternalConstraint{cap_left:0,cost:-e.value.cost,},);}else{flow[i]=e.value.max;cur_cost+=(flow[i]*e.value.cost)as i128;delta[e.source]-=e.value.max;delta[e.dest]+=e.value.max;residual.add_edge(e.source,e.dest,InternalConstraint{cap_left:0,cost:e.value.cost,},);residual.add_edge(e.dest,e.source,InternalConstraint{cap_left:e.value.max-e.value.min,cost:-e.value.cost,},);}}let mut pot=vec![0;vn];let mut positive=HashSet::new();for i in 0..vn{if delta[i]>0{positive.insert(i);}}while!positive.is_empty(){let mut q=BTreeSet::new();let mut from=vec![None;vn];let mut costs=vec![None;vn];let mut visited:Vec<bool> =vec![false;g.vs.len()];let mut negatives=vec![];for&i in positive.iter(){q.insert((0,i,None));costs[i]=Some(0);}let mut farthest=0;while let Some(&(c,i,from_edge))=q.iter().next(){q.remove(&(c,i,from_edge));if visited[i]{continue;}if delta[i]<0{negatives.push((c,i,from_edge));}from[i]=from_edge;visited[i]=true;farthest=c;for e in residual.get_outgoing_edges(i).iter(){if e.value.cap_left>0{if e.dest==e.source{continue;}if visited[e.dest]{continue;}let c=pot[e.source]-pot[e.dest]+e.value.cost+c;match costs[e.dest]{Some(cd)=>{if c<cd{costs[e.dest]=Some(c);q.insert((c,e.dest,Some(e.index)));}}None=>{costs[e.dest]=Some(c);q.insert((c,e.dest,Some(e.index)));}}}}}for i in 0..vn{if let Some(c)=costs[i]{pot[i]+=c;}else{pot[i]+=farthest;}}if negatives.is_empty(){break;}'nega_loop:for(_,i,from_edge)in negatives.into_iter(){let ei=residual.get_edge(from_edge.unwrap());let tail_node=i;let mut node=ei.source;let mut min_cap=ei.value.cap_left;let mut path=vec![from_edge.unwrap()];let mut unit_cost=ei.value.cost;while let Some(e)=from[node]{path.push(e);let edge=residual.get_edge(e);min_cap=min_cap.min(edge.value.cap_left);if min_cap==0{continue 'nega_loop;}unit_cost+=edge.value.cost;node=edge.source;}min_cap=min_cap.min(delta[node]).min(-delta[tail_node]);cur_cost+=(min_cap*unit_cost)as i128;for&i in path.iter().rev(){let edge=residual.get_edge_mut(i);edge.value.cap_left-=min_cap;let inv_edge=residual.get_edge_mut(i.bitxor(1));inv_edge.value.cap_left+=min_cap;if i&1==0{flow[i>>1]+=min_cap;}else{flow[i>>1]-=min_cap;}}delta[node]-=min_cap;delta[tail_node]+=min_cap;if delta[node]==0{positive.remove(&node);}}}for i in 0..vn{if delta[i]!=0{return Err(InfeasibleFlowResult{cost:cur_cost,flow,pot,excess:delta,});}}Ok(FlowResult{cost:cur_cost,flow,pot,})}pub fn minimum_exponent(n:i64)->usize{(64-n.saturating_sub(1).leading_zeros())as _}#[derive(Debug)]pub struct FlowResult{pub cost:i128,pub flow:Flow,pub pot:Potential,}#[derive(Debug)]pub struct InfeasibleFlowResult{pub cost:i128,pub flow:Flow,pub pot:Potential,pub excess:Vec<i64>,}pub fn mincostflow(g:&Graph<i64,Constraint>)->Result<FlowResult,InfeasibleFlowResult>{let vn=g.n_nodes();let en=g.n_edges();let mut residual:Graph<i64,InternalConstraint> =Graph::new_with_node(vn);let mut flow=vec![0;en];let mut delta=vec![0;vn];let mut pot=vec![0;vn];let mut cur_cost:i128=0;{for i in 0..vn{let node=&g.vs[i];delta[i]+=node.value;}}let mut max_cap=0i64;for i in 0..en{let e=&g.es[i];if e.value.cost>=0{flow[i]=e.value.min;cur_cost+=(flow[i]*e.value.cost)as i128;delta[e.source]-=e.value.min;delta[e.dest]+=e.value.min;let cap_left=e.value.max-e.value.min;residual.add_edge(e.source,e.dest,InternalConstraint{cap_left,cost:e.value.cost,},);residual.add_edge(e.dest,e.source,InternalConstraint{cap_left:0,cost:-e.value.cost,},);max_cap=max_cap.max(cap_left.abs());}else{flow[i]=e.value.max;cur_cost+=(flow[i]*e.value.cost)as i128;delta[e.source]-=e.value.max;delta[e.dest]+=e.value.max;let cap_left=e.value.max-e.value.min;residual.add_edge(e.source,e.dest,InternalConstraint{cap_left:0,cost:e.value.cost,},);residual.add_edge(e.dest,e.source,InternalConstraint{cap_left,cost:-e.value.cost,},);max_cap=max_cap.max(cap_left.abs());}}if max_cap!=0{let exponent=minimum_exponent(max_cap);for d_exponent in(0..=exponent).rev(){let scale=1<<d_exponent;for i in 0..(en<<1){let edge=residual.get_edge_mut(i);let c=pot[edge.source]-pot[edge.dest]+edge.value.cost;if c<0&&edge.value.cap_left>=scale{let f=edge.value.cap_left-scale+1;let c=edge.value.cost;if i&1==0{flow[i>>1]+=f;}else{flow[i>>1]-=f;}delta[edge.source]-=f;delta[edge.dest]+=f;edge.value.cap_left-=f;let inv_edge=residual.get_edge_mut(i.bitxor(1));inv_edge.value.cap_left+=f;cur_cost+=(f*c)as i128;}}let mut positive=HashSet::new();for i in 0..vn{if delta[i]>=scale{positive.insert(i);}}while!positive.is_empty(){let mut q=BTreeSet::new();let mut from=vec![None;vn];let mut costs=vec![None;vn];let mut visited:Vec<bool> =vec![false;g.vs.len()];let mut negatives=vec![];for&i in positive.iter(){q.insert((0,i,None));costs[i]=Some(0);}let mut farthest=0;while let Some(&(c,i,from_edge))=q.iter().next(){q.remove(&(c,i,from_edge));if visited[i]{continue;}if delta[i]<=-scale{negatives.push((c,i,from_edge));}from[i]=from_edge;visited[i]=true;farthest=c;for e in residual.get_outgoing_edges(i).iter(){if e.value.cap_left>=scale{if e.dest==e.source{continue;}if visited[e.dest]{continue;}let c=pot[e.source]-pot[e.dest]+e.value.cost+c;match costs[e.dest]{Some(cd)=>{if c<cd{costs[e.dest]=Some(c);q.insert((c,e.dest,Some(e.index)));}}None=>{costs[e.dest]=Some(c);q.insert((c,e.dest,Some(e.index)));}}}}}for i in 0..vn{if let Some(c)=costs[i]{pot[i]+=c;}else{pot[i]+=farthest;}}if negatives.is_empty(){break;}'nega_loop:for(_,i,from_edge)in negatives.into_iter(){let ei=residual.get_edge(from_edge.unwrap());let tail_node=i;let mut node=ei.source;let mut min_cap=ei.value.cap_left;let mut path=vec![from_edge.unwrap()];let mut unit_cost=ei.value.cost;while let Some(e)=from[node]{path.push(e);let edge=residual.get_edge(e);min_cap=min_cap.min(edge.value.cap_left);if min_cap==0{continue 'nega_loop;}unit_cost+=edge.value.cost;node=edge.source;}min_cap=min_cap.min(delta[node]).min(-delta[tail_node]);cur_cost+=(min_cap*unit_cost)as i128;for&i in path.iter().rev(){let edge=residual.get_edge_mut(i);edge.value.cap_left-=min_cap;let inv_edge=residual.get_edge_mut(i.bitxor(1));inv_edge.value.cap_left+=min_cap;if i&1==0{flow[i>>1]+=min_cap;}else{flow[i>>1]-=min_cap;}}delta[node]-=min_cap;delta[tail_node]+=min_cap;if delta[node]==0{positive.remove(&node);}}}}}for i in 0..vn{if delta[i]!=0{return Err(InfeasibleFlowResult{cost:cur_cost,flow,pot,excess:delta,});}}Ok(FlowResult{cost:cur_cost,flow,pot,})}}pub use dijkstra::{dijkstra,path_reform};}pub mod graph{use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub type EdgeId=usize;pub type NodeId=usize;#[derive(Debug)]pub struct Edge<E>{pub source:usize,pub dest:usize,pub index:usize,pub value:E,}impl<E>Edge<E>{pub fn other_side(&self,vi:usize)->usize{if vi==self.dest{self.source}else{self.dest}}}#[derive(Debug)]pub struct Vertex<V>{pub incoming:Vec<usize>,pub outgoing:Vec<usize>,pub index:usize,pub value:V,}#[derive(Debug)]pub struct Graph<V,E>{pub vs:Vec<Vertex<V>>,pub es:Vec<Edge<E>>,pub is_undirected:bool,}impl<V,E>Graph<V,E>{pub fn new()->Self{Self{vs:Vec::new(),es:Vec::new(),is_undirected:false,}}pub fn new_undirected()->Self{Self{vs:Vec::new(),es:Vec::new(),is_undirected:true,}}pub fn new_with_node(n:usize)->Self where V:Default+Clone,{let mut vs=Vec::with_capacity(n);for i in 0..n{vs.push(Vertex{incoming:Vec::new(),outgoing:Vec::new(),index:i,value:Default::default(),});}Self{vs,es:Vec::new(),is_undirected:false,}}pub fn new_undirected_with_node(n:usize)->Self where V:Default+Clone,{let mut vs=Vec::with_capacity(n);for i in 0..n{vs.push(Vertex{incoming:Vec::new(),outgoing:Vec::new(),index:i,value:Default::default(),});}Self{vs,es:Vec::new(),is_undirected:true,}}pub fn add_node(&mut self,value:V)->usize{let vi=self.vs.len();self.vs.push(Vertex{incoming:Vec::new(),outgoing:Vec::new(),index:vi,value,});self.vs.len()-1}pub fn add_edge(&mut self,source:usize,dest:usize,value:E)->usize{assert!(source<self.vs.len());assert!(dest<self.vs.len());let ei=self.es.len();self.es.push(Edge{source,dest,index:ei,value,});self.vs[source].outgoing.push(ei);self.vs[dest].incoming.push(ei);if self.is_undirected{self.vs[dest].outgoing.push(ei);self.vs[source].incoming.push(ei);}ei}pub fn get_node(&self,node:usize)->&Vertex<V>{&self.vs[node]}pub fn get_node_mut(&mut self,node:usize)->&mut Vertex<V>{&mut self.vs[node]}pub fn get_edge(&self,edge:usize)->&Edge<E>{&self.es[edge]}pub fn get_edge_mut(&mut self,edge:usize)->&mut Edge<E>{&mut self.es[edge]}pub fn get_edges(&self,node:usize)->Vec<&Edge<E>>{let mut res=vec![];for&i in&self.vs[node].incoming{res.push(&self.es[i]);}for&i in&self.vs[node].outgoing{res.push(&self.es[i]);}res}pub fn get_outgoing_edges(&self,node:usize)->Vec<&Edge<E>>{let mut res=vec![];for&i in&self.vs[node].outgoing{res.push(&self.es[i]);}res}pub fn get_incoming_edges(&self,node:usize)->Vec<&Edge<E>>{let mut res=vec![];for&i in&self.vs[node].incoming{res.push(&self.es[i]);}res}}}pub mod prelude{use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub use super::algo::{dijkstra,path_reform};pub use super::graph::{Edge,Graph,Vertex};}pub mod uf{use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub struct UnionFind{vec:Vec<usize>,}impl UnionFind{pub fn new(size:usize)->Self{let mut vec=Vec::new();for i in 0..size{vec.push(i);}Self{vec}}pub fn find_root(&mut self,a:usize)->usize{let mut a=a;let mut stack=Vec::new();loop{let parent=self.vec[a];if parent==a{for i in stack{self.vec[i]=a;}return a;}else{stack.push(a);a=parent;}}}pub fn union(&mut self,a:usize,b:usize){let a_root=self.find_root(a);let b_root=self.find_root(b);if a_root!=b_root{self.vec[a_root]=b_root;}}pub fn is_unioned(&mut self,a:usize,b:usize)->bool{self.find_root(a)==self.find_root(b)}}}pub mod visit{use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub mod dfs{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::VecDeque;use crate::__cargo_equip::crates::minimal_lib_graph::Graph;pub struct Dfs<'a,V,E>{g:&'a Graph<V,E>,stack:VecDeque<(usize,usize)>,visited:Vec<bool>,visited_index:usize,}impl<'a,V,E>Dfs<'a,V,E>{pub fn new(g:&'a Graph<V,E>)->Self{let visited=vec![false;g.vs.len()];let mut stack=VecDeque::new();stack.push_back((0,0));Self{g,stack,visited,visited_index:0,}}}impl<'a,V,E>Iterator for Dfs<'a,V,E>{type Item=usize;fn next(&mut self)->Option<Self::Item>{'l:loop{match self.stack.back_mut(){Some(back)=>{let(node,index)=back;if!self.visited[*node]{self.visited[*node]=true;return Some(*node);}let node_v=&self.g.vs[*node];if*index<node_v.outgoing.len(){let ei=node_v.outgoing[*index];let dest=self.g.es[ei].dest;*index+=1;if!self.visited[dest]{self.stack.push_back((dest,0));}}else{self.stack.pop_back();continue 'l;}}None=>{for i in(self.visited_index+1)..self.visited.len(){if!self.visited[i]{self.visited_index=i;self.stack.push_back((i,0));continue 'l;}}return None;}}}}}}pub mod dfs_all{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::VecDeque;use crate::__cargo_equip::crates::minimal_lib_graph::Graph;pub struct DfsAll<'a,V,E>{g:&'a Graph<V,E>,stack:VecDeque<(usize,usize)>,visited:Vec<bool>,pub(in crate::__cargo_equip::crates::minimal_lib_graph)from_edge:Vec<Option<usize>>,visited_index:usize,}impl<'a,V,E>DfsAll<'a,V,E>{pub fn new(g:&'a Graph<V,E>)->Self{let visited=vec![false;g.vs.len()];let from_edge=vec![None;g.vs.len()];let mut stack=VecDeque::new();stack.push_back((0,0));Self{g,stack,from_edge,visited,visited_index:0,}}}#[derive(Debug)]pub enum Order{Pre{node:usize,from_edge:Option<usize>,},Post{node:usize,from_edge:Option<usize>,},}impl<'a,V,E>Iterator for DfsAll<'a,V,E>{type Item=Order;fn next(&mut self)->Option<Self::Item>{'l:loop{match self.stack.back_mut(){Some(back)=>{let(node,index)=back;if!self.visited[*node]{self.visited[*node]=true;return Some(Order::Pre{node:*node,from_edge:self.from_edge[*node],});}let node_v=&self.g.vs[*node];if*index<node_v.outgoing.len(){let ei=node_v.outgoing[*index];let dest=self.g.es[ei].other_side(*node);*index+=1;if!self.visited[dest]&&self.from_edge[*node]!=Some(ei){self.from_edge[dest]=Some(ei);self.stack.push_back((dest,0));}}else{let node=*node;self.stack.pop_back();return Some(Order::Post{node,from_edge:self.from_edge[node],});}}None=>{for i in(self.visited_index+1)..self.visited.len(){if!self.visited[i]{self.visited_index=i;self.stack.push_back((i,0));continue 'l;}}return None;}}}}}}pub mod dfs_post{use crate::__cargo_equip::preludes::minimal_lib_graph::*;use std::collections::VecDeque;use crate::__cargo_equip::crates::minimal_lib_graph::Graph;pub struct DfsPost<'a,V,E>{g:&'a Graph<V,E>,stack:VecDeque<(usize,usize)>,visited:Vec<bool>,visited_index:usize,}impl<'a,V,E>DfsPost<'a,V,E>{pub fn new(g:&'a Graph<V,E>)->Self{let visited=vec![false;g.vs.len()];let mut stack=VecDeque::new();stack.push_back((0,0));Self{g,stack,visited,visited_index:0,}}}impl<'a,V,E>Iterator for DfsPost<'a,V,E>{type Item=usize;fn next(&mut self)->Option<Self::Item>{'l:loop{match self.stack.back_mut(){Some(back)=>{let(node,index)=back;let node_v=&self.g.vs[*node];if*index<node_v.outgoing.len(){let ei=node_v.outgoing[*index];let dest=self.g.es[ei].dest;*index+=1;if!self.visited[dest]{self.visited[dest]=true;self.stack.push_back((dest,0));}}else{let node=*node;self.stack.pop_back();return Some(node);}}None=>{for i in(self.visited_index+1)..self.visited.len(){if!self.visited[i]{self.visited_index=i;self.stack.push_back((i,0));continue 'l;}}return None;}}}}}}pub mod prelude{use crate::__cargo_equip::preludes::minimal_lib_graph::*;pub use super::dfs::Dfs;pub use super::dfs_all::{DfsAll,Order};pub use super::dfs_post::DfsPost;}pub use prelude::*;}pub use prelude::*;}
        pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub use proconio_derive::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;pub enum Chars{}pub enum Bytes{}pub enum Usize1{}pub enum Isize1{}}pub mod read{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::marker::{Bytes,Chars,Isize1,Usize1};use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;impl<T:FromStr>Readable for T where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}impl Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap().bytes().collect()}}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::io::BufRead;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R>>Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Self::Output;}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::__Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input.  ","This is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));lock.is_empty()}}
        pub mod __proconio_derive_0_1_9 {pub use crate::__cargo_equip::macros::__proconio_derive_0_1_9::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_1_9_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.1.9` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_1_9_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.1.9` should have been expanded");)}}
    }

    pub(crate) mod macros {
        pub mod lazy_static {pub use crate::{__cargo_equip_macro_def_lazy_static___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def_lazy_static___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def_lazy_static_lazy_static as lazy_static};}
        pub mod __minimal_lib_algo_0_1_0 {}
        pub mod minimal_lib_graph {}
        pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};}
        pub mod __proconio_derive_0_1_9 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_1_9_derive_readable as derive_readable,__cargo_equip_macro_def___proconio_derive_0_1_9_fastout as fastout};}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::lazy_static::*};}

    mod preludes {
        pub mod lazy_static {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::lazy_static::*;}
        pub mod __minimal_lib_algo_0_1_0 {}
        pub mod minimal_lib_graph {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__minimal_lib_algo_0_1_0 as minimal_lib_algo;}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::lazy_static::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{lazy_static,__proconio_derive_0_1_9 as proconio_derive};}
        pub mod __proconio_derive_0_1_9 {}
    }
}