結果
問題 | No.1254 補強への架け橋 |
ユーザー | 37kt |
提出日時 | 2023-12-26 10:43:49 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 731 ms / 2,000 ms |
コード長 | 26,586 bytes |
コンパイル時間 | 1,904 ms |
コンパイル使用メモリ | 207,912 KB |
実行使用メモリ | 136,432 KB |
最終ジャッジ日時 | 2023-12-26 10:44:19 |
合計ジャッジ時間 | 28,921 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,676 KB |
testcase_01 | AC | 1 ms
6,676 KB |
testcase_02 | AC | 1 ms
6,676 KB |
testcase_03 | AC | 1 ms
6,676 KB |
testcase_04 | AC | 1 ms
6,676 KB |
testcase_05 | AC | 1 ms
6,676 KB |
testcase_06 | AC | 1 ms
6,676 KB |
testcase_07 | AC | 1 ms
6,676 KB |
testcase_08 | AC | 1 ms
6,676 KB |
testcase_09 | AC | 1 ms
6,676 KB |
testcase_10 | AC | 1 ms
6,676 KB |
testcase_11 | AC | 1 ms
6,676 KB |
testcase_12 | AC | 1 ms
6,676 KB |
testcase_13 | AC | 1 ms
6,676 KB |
testcase_14 | AC | 1 ms
6,676 KB |
testcase_15 | AC | 1 ms
6,676 KB |
testcase_16 | AC | 1 ms
6,676 KB |
testcase_17 | AC | 1 ms
6,676 KB |
testcase_18 | AC | 1 ms
6,676 KB |
testcase_19 | AC | 1 ms
6,676 KB |
testcase_20 | AC | 1 ms
6,676 KB |
testcase_21 | AC | 1 ms
6,676 KB |
testcase_22 | AC | 1 ms
6,676 KB |
testcase_23 | AC | 1 ms
6,676 KB |
testcase_24 | AC | 1 ms
6,676 KB |
testcase_25 | AC | 1 ms
6,676 KB |
testcase_26 | AC | 1 ms
6,676 KB |
testcase_27 | AC | 1 ms
6,676 KB |
testcase_28 | AC | 1 ms
6,676 KB |
testcase_29 | AC | 1 ms
6,676 KB |
testcase_30 | AC | 1 ms
6,676 KB |
testcase_31 | AC | 1 ms
6,676 KB |
testcase_32 | AC | 1 ms
6,676 KB |
testcase_33 | AC | 1 ms
6,676 KB |
testcase_34 | AC | 1 ms
6,676 KB |
testcase_35 | AC | 1 ms
6,676 KB |
testcase_36 | AC | 1 ms
6,676 KB |
testcase_37 | AC | 1 ms
6,676 KB |
testcase_38 | AC | 1 ms
6,676 KB |
testcase_39 | AC | 1 ms
6,676 KB |
testcase_40 | AC | 1 ms
6,676 KB |
testcase_41 | AC | 1 ms
6,676 KB |
testcase_42 | AC | 1 ms
6,676 KB |
testcase_43 | AC | 4 ms
6,676 KB |
testcase_44 | AC | 2 ms
6,676 KB |
testcase_45 | AC | 2 ms
6,676 KB |
testcase_46 | AC | 3 ms
6,676 KB |
testcase_47 | AC | 3 ms
6,676 KB |
testcase_48 | AC | 3 ms
6,676 KB |
testcase_49 | AC | 1 ms
6,676 KB |
testcase_50 | AC | 5 ms
6,676 KB |
testcase_51 | AC | 4 ms
6,676 KB |
testcase_52 | AC | 4 ms
6,676 KB |
testcase_53 | AC | 3 ms
6,676 KB |
testcase_54 | AC | 4 ms
6,676 KB |
testcase_55 | AC | 4 ms
6,676 KB |
testcase_56 | AC | 1 ms
6,676 KB |
testcase_57 | AC | 3 ms
6,676 KB |
testcase_58 | AC | 3 ms
6,676 KB |
testcase_59 | AC | 1 ms
6,676 KB |
testcase_60 | AC | 2 ms
6,676 KB |
testcase_61 | AC | 4 ms
6,676 KB |
testcase_62 | AC | 1 ms
6,676 KB |
testcase_63 | AC | 52 ms
14,964 KB |
testcase_64 | AC | 12 ms
6,676 KB |
testcase_65 | AC | 32 ms
9,732 KB |
testcase_66 | AC | 23 ms
8,120 KB |
testcase_67 | AC | 8 ms
6,676 KB |
testcase_68 | AC | 28 ms
8,832 KB |
testcase_69 | AC | 36 ms
10,624 KB |
testcase_70 | AC | 14 ms
6,676 KB |
testcase_71 | AC | 11 ms
6,676 KB |
testcase_72 | AC | 37 ms
10,532 KB |
testcase_73 | AC | 12 ms
6,676 KB |
testcase_74 | AC | 36 ms
10,384 KB |
testcase_75 | AC | 26 ms
8,604 KB |
testcase_76 | AC | 5 ms
6,676 KB |
testcase_77 | AC | 22 ms
7,848 KB |
testcase_78 | AC | 46 ms
13,500 KB |
testcase_79 | AC | 48 ms
13,960 KB |
testcase_80 | AC | 40 ms
11,392 KB |
testcase_81 | AC | 47 ms
14,040 KB |
testcase_82 | AC | 43 ms
12,964 KB |
testcase_83 | AC | 669 ms
130,712 KB |
testcase_84 | AC | 661 ms
128,540 KB |
testcase_85 | AC | 383 ms
77,688 KB |
testcase_86 | AC | 568 ms
114,540 KB |
testcase_87 | AC | 606 ms
121,052 KB |
testcase_88 | AC | 79 ms
20,040 KB |
testcase_89 | AC | 659 ms
130,268 KB |
testcase_90 | AC | 398 ms
79,252 KB |
testcase_91 | AC | 313 ms
66,424 KB |
testcase_92 | AC | 153 ms
35,156 KB |
testcase_93 | AC | 507 ms
103,644 KB |
testcase_94 | AC | 471 ms
101,636 KB |
testcase_95 | AC | 464 ms
99,340 KB |
testcase_96 | AC | 628 ms
126,888 KB |
testcase_97 | AC | 259 ms
58,000 KB |
testcase_98 | AC | 636 ms
127,940 KB |
testcase_99 | AC | 355 ms
71,976 KB |
testcase_100 | AC | 687 ms
136,432 KB |
testcase_101 | AC | 134 ms
31,844 KB |
testcase_102 | AC | 67 ms
17,448 KB |
testcase_103 | AC | 147 ms
33,700 KB |
testcase_104 | AC | 219 ms
51,592 KB |
testcase_105 | AC | 526 ms
109,304 KB |
testcase_106 | AC | 284 ms
61,488 KB |
testcase_107 | AC | 669 ms
133,140 KB |
testcase_108 | AC | 667 ms
128,968 KB |
testcase_109 | AC | 515 ms
105,824 KB |
testcase_110 | AC | 467 ms
98,772 KB |
testcase_111 | AC | 496 ms
105,620 KB |
testcase_112 | AC | 198 ms
43,972 KB |
testcase_113 | AC | 445 ms
86,216 KB |
testcase_114 | AC | 285 ms
59,564 KB |
testcase_115 | AC | 84 ms
20,720 KB |
testcase_116 | AC | 329 ms
67,556 KB |
testcase_117 | AC | 209 ms
48,356 KB |
testcase_118 | AC | 627 ms
125,764 KB |
testcase_119 | AC | 361 ms
72,708 KB |
testcase_120 | AC | 615 ms
122,404 KB |
testcase_121 | AC | 169 ms
37,192 KB |
testcase_122 | AC | 321 ms
67,436 KB |
testcase_123 | AC | 1 ms
6,676 KB |
testcase_124 | AC | 731 ms
135,316 KB |
testcase_125 | AC | 728 ms
135,328 KB |
ソースコード
pub use __cargo_equip::prelude::*; use offline_dynamic_connectivity::{OfflineDynamicConnectivity, QueryResult}; #[allow(unused_imports)] use proconio::{ input, marker::{Bytes, Chars, Usize1}, }; fn main() { input! { n: usize, ab: [(Usize1, Usize1); n], } let mut dc = OfflineDynamicConnectivity::new(n); for &(a, b) in &ab { dc.add_edge(a, b); } for i in 0..n { let (a, b) = ab[i]; dc.remove_edge(a, b); dc.same(a, b); dc.add_edge(a, b); } let dc = dc.build(); let mut res = vec![]; for i in 0..n { if let QueryResult::Same(f) = dc[i] { if f { res.push(i); } } } println!("{}", res.len()); for i in res { print!("{} ", i + 1); } println!(); } // 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_1_4_0` /// - `offline-dynamic-connectivity 0.1.0 (path+███████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::offline_dynamic_connectivity` /// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio` /// - `rollback-union-find 0.1.0 (path+███████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::rollback_union_find` /// /// # Procedural macros /// /// - `proconio-derive 0.2.1 (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.4.3 (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_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;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_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___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_1_4_0::__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_1_4_0::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_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_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_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}} pub mod offline_dynamic_connectivity {use crate::__cargo_equip::preludes::offline_dynamic_connectivity::*;use std::collections::BTreeMap;use rollback_union_find::RollbackUnionFind;enum ReadQuery{Leader(usize),Same(usize,usize),Size(usize),Count,}#[derive(Clone,Copy,Debug,PartialEq,Eq)]pub enum QueryResult{Leader(usize),Same(bool),Size(usize),Count(usize),}pub struct OfflineDynamicConnectivity{built:bool,query_cnt:usize,component_cnt:usize,edge_cnt:BTreeMap<(usize,usize),usize>,appear:BTreeMap<(usize,usize),usize>,edges:Vec<((usize,usize),(usize,usize))>,reads:Vec<(usize,ReadQuery)>,ri:usize,res:Vec<QueryResult>,segsz:usize,seg:Vec<Vec<(usize,usize)>>,uf:RollbackUnionFind,}impl OfflineDynamicConnectivity{pub fn new(n:usize)->Self{Self{built:false,query_cnt:0,component_cnt:n,edge_cnt:BTreeMap::new(),appear:BTreeMap::new(),edges:vec![],reads:vec![],ri:0,res:vec![],segsz:0,seg:vec![],uf:RollbackUnionFind::new(n),}}pub fn add_edge(&mut self,x:usize,y:usize){assert!(!self.built);let e=(x.min(y),x.max(y));self.edge_cnt.entry(e).and_modify(|e|*e+=1).or_insert(1);if self.edge_cnt[&e]==1{self.appear.insert(e,self.query_cnt);}self.query_cnt+=1;}pub fn remove_edge(&mut self,x:usize,y:usize){assert!(!self.built);let e=(x.min(y),x.max(y));self.edge_cnt.entry(e).and_modify(|e|*e-=1);if self.edge_cnt[&e]==0{self.edges.push((e,(self.appear[&e],self.query_cnt)));}self.query_cnt+=1;}pub fn leader(&mut self,x:usize)->usize{assert!(!self.built);self.reads.push((self.query_cnt,ReadQuery::Leader(x)));self.query_cnt+=1;self.reads.len()-1}pub fn same(&mut self,x:usize,y:usize)->usize{assert!(!self.built);self.reads.push((self.query_cnt,ReadQuery::Same(x,y)));self.query_cnt+=1;self.reads.len()-1}pub fn size(&mut self,x:usize)->usize{assert!(!self.built);self.reads.push((self.query_cnt,ReadQuery::Size(x)));self.query_cnt+=1;self.reads.len()-1}pub fn count(&mut self)->usize{assert!(!self.built);self.reads.push((self.query_cnt,ReadQuery::Count));self.query_cnt+=1;self.reads.len()-1}pub fn build(&mut self)->Vec<QueryResult>{assert!(!self.built);self.built=true;for(&e,&c)in&self.edge_cnt{if c>0{self.edges.push((e,(self.appear[&e],self.query_cnt)));}}self.segsz=1;while self.segsz<self.query_cnt{self.segsz*=2;}self.seg=vec![vec![];self.segsz*2];for&((x,y),(l,r))in&self.edges.clone(){self.add(l,r,(x,y),1,0,self.segsz);}self.dfs(1);self.res.clone()}fn add(&mut self,a:usize,b:usize,e:(usize,usize),k:usize,l:usize,r:usize){if b<=l||r<=a{return;}if a<=l&&r<=b{self.seg[k].push(e);return;}let m=(l+r)/2;self.add(a,b,e,k*2,l,m);self.add(a,b,e,k*2+1,m,r);}fn dfs(&mut self,k:usize){let mut merge_cnt=0;for&(x,y)in&self.seg[k]{if self.uf.merge(x,y){merge_cnt+=1;}}self.component_cnt-=merge_cnt;if k<self.segsz{self.dfs(k*2);self.dfs(k*2+1);}else if self.ri<self.reads.len()&&self.reads[self.ri].0==k-self.segsz{match self.reads[self.ri].1{ReadQuery::Leader(x)=>{self.res.push(QueryResult::Leader(self.uf.leader(x)));}ReadQuery::Same(x,y)=>{self.res.push(QueryResult::Same(self.uf.same(x,y)));}ReadQuery::Size(x)=>{self.res.push(QueryResult::Size(self.uf.size(x)));}ReadQuery::Count=>{self.res.push(QueryResult::Count(self.component_cnt));}}self.ri+=1;}for _ in 0..self.seg[k].len(){self.uf.undo();}self.component_cnt+=merge_cnt;}}} 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::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}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()}}pub enum Bytes{}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()}}pub enum Usize1{}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")}}pub enum Isize1{}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::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;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;}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,),}}}}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_2_1 {pub use crate::__cargo_equip::macros::__proconio_derive_0_2_1::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.2.1` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}} pub mod rollback_union_find {use std::mem::swap;#[derive(Clone)]pub struct RollbackUnionFind{par:Vec<i32>,his:Vec<(usize,i32)>,}impl RollbackUnionFind{pub fn new(n:usize)->Self{Self{par:vec![-1;n],his:vec![],}}pub fn len(&self)->usize{self.par.len()}pub fn merge(&mut self,x:usize,y:usize)->bool{let mut x=self.leader(x);let mut y=self.leader(y);self.his.push((x,self.par[x]));self.his.push((y,self.par[y]));if x==y{return false;}if-self.par[x]< -self.par[y]{swap(&mut x,&mut y);}self.par[x]+=self.par[y];self.par[y]=x as i32;true}pub fn leader(&self,mut x:usize)->usize{while self.par[x]>=0{x=self.par[x]as usize;}x}pub fn same(&self,x:usize,y:usize)->bool{self.leader(x)==self.leader(y)}pub fn size(&self,x:usize)->usize{-self.par[self.leader(x)]as usize}pub fn undo(&mut self){for _ in 0..2{let(x,par)=self.his.pop().unwrap();self.par[x]=par;}}pub fn groups(&self)->Vec<Vec<usize>>{let mut res=vec![vec![];self.len()];for x in 0..self.len(){res[self.leader(x)].push(x);}res.into_iter().filter(|g|g.len()>0).collect()}}} } pub(crate) mod macros { pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};} pub mod offline_dynamic_connectivity {} 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_2_1 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable as derive_readable,__cargo_equip_macro_def___proconio_derive_0_2_1_fastout as fastout};} pub mod rollback_union_find {} } pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};} mod preludes { pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;} pub mod offline_dynamic_connectivity {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::rollback_union_find;} pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__lazy_static_1_4_0 as lazy_static,__proconio_derive_0_2_1 as proconio_derive};} pub mod __proconio_derive_0_2_1 {} pub mod rollback_union_find {} } }