use crate::{segtree::Segtree, uf_checklist::UfChecklist}; use fp::F1000000007 as Fp; use hld::Hld; use ngtio::with_stdin; use std::{collections::HashMap, iter::repeat_with, mem::swap, ops::Add}; use union_find::UnionFind; fn main() { let mut buf = with_stdin(); let n = buf.usize(); let m = buf.usize(); let edges = repeat_with(|| [buf.usize() - 1, buf.usize() - 1]) .take(m) .collect::>(); let q = buf.usize(); let queries = repeat_with(|| ([buf.usize() - 1, buf.usize() - 1], buf.usize() - 1)) .take(q) .collect::>(); let ans = solve(n, &edges, &queries); for ans in &ans { if let Some(ans) = ans { println!("{}", ans); } else { println!("-1"); } } } fn solve(n: usize, edges: &[[usize; 2]], queries: &[([usize; 2], usize)]) -> Vec> { let m = edges.len(); // MST を構築して、辺をストックです。 let mut uf = UnionFind::new(n); let mut mst = vec![Vec::new(); n]; let mut map = HashMap::new(); let mut in_mst = vec![false; m]; for (i, &[u, v]) in edges.iter().enumerate() { if !uf.same(u, v) { uf.union(u, v); mst[u].push(v); mst[v].push(u); in_mst[i] = true; } map.insert([u, v], i); map.insert([v, u], i); } // 回避予行演習です。 let mut ufc = UfChecklist::new(m); let hld = Hld::new(0, &mut mst); let mut forb_e_to_avoid_e = vec![None; m]; for (avoid_e, &[u, v]) in edges.iter().enumerate().filter(|&(i, _)| !in_mst[i]) { for (l, r) in hld.iter_e(u, v) { for forb_e in ufc.range_check(l..=r).map(|i| { let x = hld.ord()[i]; let p = hld.parent()[x]; assert_ne!(x, p); map[&[p, x]] }) { if forb_e_to_avoid_e[forb_e].is_none() { forb_e_to_avoid_e[forb_e] = Some(avoid_e); } } } } // 辺の重みをセグツリーに載せておきます。 let seg_time_to_weight = Segtree::new( &hld.ord() .iter() .map(|&i| { let p = hld.parent()[i]; if i == p { Fp::new(0) } else { Fp::new(2).pow(map[&[p, i]] as u32 + 1) } }) .collect::>(), Add::add, || Fp::new(0), ); // クエリ処理パートです。 queries .iter() .map(|&([end_v0, end_v1], forb_e)| { let [mut forb_v0, mut forb_v1] = edges[forb_e]; if hld.time()[forb_v0] > hld.time()[forb_v1] { swap(&mut forb_v0, &mut forb_v1); } if in_mst[forb_e] && hld.between(end_v0, forb_v0, end_v1) && hld.between(end_v0, forb_v1, end_v1) { // 回避が必要な場合 forb_e_to_avoid_e[forb_e].map(|avoid_e| { let avoid_cost = Fp::new(2).pow(avoid_e as u32 + 1); let [avoid_v0, avoid_v1] = edges[avoid_e]; if hld.dist(end_v0, avoid_v0) + hld.dist(avoid_v1, end_v1) < hld.dist(end_v0, avoid_v1) + hld.dist(avoid_v0, end_v1) { hld.iter_e(end_v0, avoid_v0) .map(|(l, r)| seg_time_to_weight.fold(l..=r)) .sum::() + avoid_cost + hld .iter_e(avoid_v1, end_v1) .map(|(l, r)| seg_time_to_weight.fold(l..=r)) .sum::() } else { hld.iter_e(end_v0, avoid_v1) .map(|(l, r)| seg_time_to_weight.fold(l..=r)) .sum::() + avoid_cost + hld .iter_e(avoid_v0, end_v1) .map(|(l, r)| seg_time_to_weight.fold(l..=r)) .sum::() } }) } else { // 回避不要な場合 Some( hld.iter_e(end_v0, end_v1) .map(|(l, r)| seg_time_to_weight.fold(l..=r)) .sum::(), ) } }) .collect::>() } #[cfg(test)] mod tests { use super::{solve, union_find::UnionFind, Fp}; use make_graph::array_make_undirected_weighted; use rand::{ prelude::{SliceRandom, StdRng}, Rng, SeedableRng, }; use std::{ cmp::Reverse, collections::{BinaryHeap, HashSet}, iter::repeat_with, mem::swap, u64::MAX, }; #[test] fn test_solve() { let mut rng = StdRng::seed_from_u64(42); for _ in 0..500 { let n = rng.gen_range(2, 15); let m = rng.gen_range(n - 1, (n * (n - 1) / 2 + 1).min(15)); let edges = gen_connected_graph(&mut rng, n, m); let q = n; let queries = repeat_with(|| { let [u, v] = gen_strictly_increasing_pair(&mut rng, n); let i = rng.gen_range(0, m); ([u, v], i) }) .take(q) .collect::>(); println!("n = {}, edges = {:?}, queries = {:?}", n, &edges, &queries); let result = solve(n, &edges, &queries); let expected = brute(n, &edges, &queries); assert_eq!(result, expected); } } fn gen_connected_graph(rng: &mut StdRng, n: usize, m: usize) -> Vec<[usize; 2]> { let mut uf = UnionFind::new(n); let mut edges = HashSet::new(); for _ in 0..n - 1 { loop { let [u, v] = gen_strictly_increasing_pair(rng, n); if !uf.same(u, v) { uf.union(u, v); edges.insert([u, v]); break; } } } for _ in 0..m - (n - 1) { loop { let [u, v] = gen_strictly_increasing_pair(rng, n); if !edges.contains(&[u, v]) { edges.insert([u, v]); break; } } } let mut edges = edges.into_iter().collect::>(); edges.shuffle(rng); edges } fn gen_strictly_increasing_pair(rng: &mut StdRng, n: usize) -> [usize; 2] { let mut u = rng.gen_range(0, n - 1); let mut v = rng.gen_range(0, n); if u >= v { swap(&mut u, &mut v); v += 1; } assert!(u < v); [u, v] } fn brute(n: usize, edges: &[[usize; 2]], queries: &[([usize; 2], usize)]) -> Vec> { let edges = edges .into_iter() .enumerate() .map(|(i, &[u, v])| ([u, v], 2u64.pow(i as u32 + 1))) .collect::>(); let mut g = array_make_undirected_weighted(n, edges.as_slice()); queries .iter() .map(|&([u, v], e)| { let ([e0, e1], w) = edges[e]; remove_item(&mut g[e0], &(e1, w)); remove_item(&mut g[e1], &(e0, w)); let mut dist = vec![MAX; n]; dist[u] = 0; let mut heap = BinaryHeap::from(vec![(Reverse(0), u)]); while let Some((Reverse(dx), x)) = heap.pop() { if dist[x] < dx { continue; } for &(y, w) in &g[x] { let dy = dx + w; if dy < dist[y] { heap.push((Reverse(dy), y)); dist[y] = dy; } } } g[e0].push((e1, w)); g[e1].push((e0, w)); if dist[v] == MAX { None } else { Some(Fp::from(dist[v])) } }) .collect::>() } fn remove_item(me: &mut Vec, item: &V) -> Option where T: PartialEq, { let pos = me.iter().position(|x| *x == *item)?; Some(me.remove(pos)) } // bfs {{{ #[allow(dead_code)] mod bfs { use std::collections::VecDeque; pub fn tree_diamter(g: &[Vec]) -> ([usize; 2], u32) { assert_eq!(g.iter().flatten().count(), (g.len() - 1) * 2); let dist = calc_dist(0, g); let &diam = dist.iter().max().unwrap(); let x = dist.iter().position(|&d| d == diam).unwrap(); let dist = calc_dist(x, g); let &diam = dist.iter().max().unwrap(); let y = dist.iter().position(|&d| d == diam).unwrap(); ([x, y], diam) } pub fn tree_diamter_restore(g: &[Vec]) -> (Vec, u32) { assert_eq!(g.iter().flatten().count(), (g.len() - 1) * 2); let dist = calc_dist(0, g); let &diam = dist.iter().max().unwrap(); let x = dist.iter().position(|&d| d == diam).unwrap(); let (dist, prv) = calc_dist_restore(x, g); let &diam = dist.iter().max().unwrap(); let mut res = vec![dist.iter().position(|&d| d == diam).unwrap()]; loop { let x = *res.last().unwrap(); if dist[x] == 0 { break; } res.push(prv[x]); } (res, diam) } pub fn calc_dist(start: usize, g: &[Vec]) -> Vec { let mut dist = vec![std::u32::MAX; g.len()]; dist[start] = 0; let mut queue = VecDeque::from(vec![start]); while let Some(x) = queue.pop_front() { for &y in &g[x] { if dist[y] == std::u32::MAX { dist[y] = dist[x] + 1; queue.push_back(y); } } } dist } pub fn calc_dist_restore(start: usize, g: &[Vec]) -> (Vec, Vec) { let mut dist = vec![std::u32::MAX; g.len()]; let mut prv = vec![std::usize::MAX; g.len()]; dist[start] = 0; prv[start] = start; let mut queue = VecDeque::from(vec![start]); while let Some(x) = queue.pop_front() { for &y in &g[x] { if dist[y] == std::u32::MAX { dist[y] = dist[x] + 1; prv[y] = x; queue.push_back(y); } } } (dist, prv) } pub fn find_path(start: usize, end: usize, g: &[Vec]) -> Option> { let (dist, prv) = calc_dist_restore(start, g); if dist[end] == std::u32::MAX { None } else { let mut res = vec![end]; loop { let x = *res.last().unwrap(); if x == start { res.reverse(); return Some(res); } res.push(prv[x]); } } } } // }}} // make_graph {{{ #[allow(dead_code)] mod make_graph { pub fn tuple_make_undirected(n: usize, edges: &[(usize, usize)]) -> Vec> { make_undirected_by(n, edges, |&(u, v)| [u, v]) } pub fn array_make_undirected(n: usize, edges: &[[usize; 2]]) -> Vec> { make_undirected_by(n, edges, |&[u, v]| [u, v]) } pub fn make_undirected_by( n: usize, edges: &[E], f: impl Fn(&E) -> [usize; 2], ) -> Vec> { let mut g = vec![Vec::new(); n]; for [u, v] in edges.iter().map(f) { g[u].push(v); g[v].push(u); } g } pub fn tuple_make_directed(n: usize, edges: &[(usize, usize)]) -> Vec> { make_directed_by(n, edges, |&(u, v)| [u, v]) } pub fn array_make_directed(n: usize, edges: &[[usize; 2]]) -> Vec> { make_directed_by(n, edges, |&[u, v]| [u, v]) } pub fn make_directed_by( n: usize, edges: &[E], f: impl Fn(&E) -> [usize; 2], ) -> Vec> { let mut g = vec![Vec::new(); n]; edges.iter().map(f).for_each(|[u, v]| g[u].push(v)); g } pub fn tuple_make_undirected_weighted( n: usize, edges: &[(usize, usize, T)], ) -> Vec> { make_undirected_weighted_by(n, edges, |&(u, v, x)| ([u, v], x)) } pub fn array_make_undirected_weighted( n: usize, edges: &[([usize; 2], T)], ) -> Vec> { make_undirected_weighted_by(n, edges, |&([u, v], x)| ([u, v], x)) } pub fn make_undirected_weighted_by( n: usize, edges: &[E], f: impl Fn(&E) -> ([usize; 2], T), ) -> Vec> { let mut g = vec![Vec::new(); n]; for ([u, v], x) in edges.iter().map(f) { g[u].push((v, x)); g[v].push((u, x)); } g } pub fn tuple_make_directed_weighted( n: usize, edges: &[(usize, usize, T)], ) -> Vec> { make_directed_weighted_by(n, edges, |&(u, v, x)| ([u, v], x)) } pub fn array_make_directed_weighted( n: usize, edges: &[([usize; 2], T)], ) -> Vec> { make_directed_weighted_by(n, edges, |&([u, v], x)| ([u, v], x)) } pub fn make_directed_weighted_by( n: usize, edges: &[E], f: impl Fn(&E) -> ([usize; 2], T), ) -> Vec> { let mut g = vec![Vec::new(); n]; edges .iter() .map(f) .for_each(|([u, v], w)| g[u].push((v, w))); g } } // }}} } // uf_checklist {{{ #[allow(dead_code)] mod uf_checklist { use { crate::union_find::UnionFind, std::ops::{Bound, Range, RangeBounds}, }; #[derive(Clone, Debug)] pub struct UfChecklist { uf: UnionFind, rightmost: Vec, } impl UfChecklist { pub fn new(n: usize) -> Self { Self { uf: UnionFind::new(n + 1), rightmost: (0..=n).collect::>(), } } pub fn range_check(&mut self, range: impl RangeBounds) -> Iter<'_> { let n = self.rightmost.len() - 1; let Range { mut start, end } = open(range, n); assert!( start <= end && end <= n, "範囲外です。start = {}, end = {}, n = {}", start, end, n ); start = __next_unckecked_cell(self, start); Iter { range_check: self, start, end, } } pub fn lower_bound(&self, i: usize) -> Option { let n = self.rightmost.len() - 1; assert!(i < n, "範囲外です。 i = {}, n = {}", i, n); let i = __next_unckecked_cell(self, i); if i == self.rightmost.len() - 1 { None } else { Some(i) } } pub fn is_checked(&self, i: usize) -> bool { let n = self.rightmost.len() - 1; assert!(i < n, "範囲外です。 i = {}, n = {}", i, n); self.rightmost[self.uf.find(i)] != i } pub fn check(&mut self, i: usize) -> bool { let n = self.rightmost.len() - 1; assert!(i < n, "範囲外です。 i = {}, n = {}", i, n); if self.rightmost[self.uf.find(i)] == i { let next = __next_unckecked_cell(self, i + 1); self.uf.union(i, next); self.rightmost[self.uf.find(next)] = next; true } else { false } } } fn __next_unckecked_cell(range_check: &UfChecklist, i: usize) -> usize { range_check.rightmost[range_check.uf.find(i)] } #[derive(Debug)] pub struct Iter<'a> { range_check: &'a mut UfChecklist, start: usize, end: usize, } impl Iterator for Iter<'_> { type Item = usize; fn next(&mut self) -> Option { let Self { range_check, start, end, } = self; if *start < *end { let ans = *start; let check_result = range_check.check(*start); assert!(check_result); let next = __next_unckecked_cell(&range_check, *start); *start = next; Some(ans) } else { None } } } fn open(range: impl RangeBounds, len: usize) -> Range { (match range.start_bound() { Bound::Unbounded => 0, Bound::Included(&x) => x, Bound::Excluded(&x) => x + 1, })..match range.end_bound() { Bound::Excluded(&x) => x, Bound::Included(&x) => x + 1, Bound::Unbounded => len, } } // dbg {{{ #[allow(dead_code)] mod dbg { mod bitslice { use std::fmt::{self, Debug, Display, Formatter}; pub struct BitSlice<'a>(pub &'a [bool]); impl<'a> Display for BitSlice<'a> { fn fmt(&self, w: &mut Formatter) -> fmt::Result { write!( w, "{}", self.0 .iter() .map(|&b| if b { '1' } else { '0' }) .collect::() ) } } impl<'a> Debug for BitSlice<'a> { fn fmt(&self, w: &mut Formatter) -> fmt::Result { write!(w, "{}", self) } } } mod table { use std::{ fmt::{self, Debug, Formatter}, marker::PhantomData, }; pub fn table(table: &[U]) -> Table<'_, T, U> { Table { _marker: PhantomData, table, } } pub struct Table<'a, T, U> { table: &'a [U], _marker: PhantomData, } impl<'a, T, U> Clone for Table<'a, T, U> { fn clone(&self) -> Self { Self { table: self.table, _marker: PhantomData, } } } impl<'a, T, U> Copy for Table<'a, T, U> {} impl<'a, T, U> Debug for Table<'a, T, U> where T: Debug, U: AsRef<[T]>, { fn fmt(&self, w: &mut Formatter) -> fmt::Result { write!(w, "{:?}", self.by(|cell| format!("{:?}", cell))) } } impl<'a, T, U> Table<'a, T, U> { pub fn by(self, f: F) -> TableF<'a, T, U, F> where T: Debug, U: AsRef<[T]>, F: Fn(&T) -> String, { TableF { _marker: PhantomData, table: self.table, f, } } } pub struct TableF<'a, T, U, F> { pub _marker: PhantomData, pub table: &'a [U], pub f: F, } impl<'a, T, U, F: Clone> Clone for TableF<'a, T, U, F> { fn clone(&self) -> Self { Self { table: self.table, _marker: PhantomData, f: self.f.clone(), } } } impl<'a, T, U, F: Copy> Copy for TableF<'a, T, U, F> {} impl<'a, T, U, F> Debug for TableF<'a, T, U, F> where T: Debug, U: AsRef<[T]>, F: Fn(&T) -> String, { fn fmt(&self, w: &mut Formatter) -> fmt::Result { self.table .iter() .enumerate() .try_for_each(|(row_index, row)| { writeln!( w, "{:02}|{}", row_index, row.as_ref() .iter() .map(|cell| format!(" {}", (&self.f)(cell))) .collect::() ) }) } } } pub use { bitslice::BitSlice, table::{table, Table}, }; #[macro_export] macro_rules! lg { (@nl $value:expr) => { eprintln!("[{}:{}]", file!(), line!()); match $value { value => { eprint!("{:?}", &value); } } }; (@contents $head:expr $(,)?) => { match $head { head => { eprintln!(" {} = {:?}", stringify!($head), &head); } } }; (@contents $head:expr $(,$tail:expr)+ $(,)?) => { match $head { head => { eprint!(" {} = {:?},", stringify!($head), &head); } } $crate::lg!(@contents $($tail),*); }; ($($expr:expr),* $(,)?) => { eprint!("[{}:{}]", file!(), line!()); $crate::lg!(@contents $($expr),*) }; } } // }}} } // }}} // hld {{{ #[allow(dead_code)] mod hld { use std::{mem::swap, usize::MAX}; #[derive(Clone, Debug, Default, Hash, PartialEq)] pub struct Hld { time: Vec, ord: Vec, parent: Vec, head: Vec, } impl Hld { pub fn new(root: usize, g: &mut [Vec]) -> Self { let (time, ord, parent, head) = hld(root, g); Self { time, ord, parent, head, } } pub fn time(&self) -> &[usize] { &self.time } pub fn ord(&self) -> &[usize] { &self.ord } pub fn parent(&self) -> &[usize] { &self.parent } pub fn head(&self) -> &[usize] { &self.head } pub fn dist(&self, u: usize, v: usize) -> usize { self.iter_e(u, v).map(|(l, r)| r - l + 1).sum::() } pub fn lca(&self, u: usize, v: usize) -> usize { let (u, v) = self.iter_v(u, v).last().unwrap(); self.ord[u.min(v)] } pub fn between(&self, a: usize, b: usize, c: usize) -> bool { let mid = self.time[b]; self.iter_v(a, c) .any(|(left, right)| (left..=right).contains(&mid)) } pub fn iter_v(&self, u: usize, v: usize) -> IterV<'_> { IterV { hld: self, u, v, finish: false, } } pub fn iter_e(&self, u: usize, v: usize) -> IterE<'_> { IterE { hld: self, u, v, finish: false, } } } #[derive(Clone, Debug, Hash, PartialEq, Copy)] pub struct IterV<'a> { hld: &'a Hld, u: usize, v: usize, finish: bool, } impl Iterator for IterV<'_> { type Item = (usize, usize); fn next(&mut self) -> Option { if self.finish { return None; } let Self { hld, u, v, .. } = self; if hld.time[*u] > hld.time[*v] { swap(u, v); } Some(if hld.head[*u] != hld.head[*v] { let h = hld.head[*v]; let ans = (hld.time[h], hld.time[*v]); assert_ne!(hld.parent[h], h, "入力のグラフが非連結です。"); *v = hld.parent[h]; ans } else { self.finish = true; (hld.time[*u], hld.time[*v]) }) } } #[derive(Clone, Debug, Hash, PartialEq, Copy)] pub struct IterE<'a> { hld: &'a Hld, u: usize, v: usize, finish: bool, } impl Iterator for IterE<'_> { type Item = (usize, usize); fn next(&mut self) -> Option { if self.finish { return None; } let Self { hld, u, v, .. } = self; if hld.time[*u] > hld.time[*v] { swap(u, v); } if hld.head[*u] != hld.head[*v] { let h = hld.head[*v]; let ans = (hld.time[h], hld.time[*v]); assert_ne!(hld.parent[h], h, "入力のグラフが非連結です。"); *v = hld.parent[h]; Some(ans) } else { self.finish = true; if *u == *v { None } else { Some((hld.time[*u] + 1, hld.time[*v])) } } } } fn hld(root: usize, g: &mut [Vec]) -> (Vec, Vec, Vec, Vec) { dfs(root, root, g); let mut ord = Vec::new(); let mut time = vec![MAX; g.len()]; let mut parent = vec![MAX; g.len()]; let mut head = vec![MAX; g.len()]; parent[root] = root; head[root] = root; efs(root, &g, &mut time, &mut ord, &mut parent, &mut head); assert!(parent.iter().all(|&x| x != MAX), "入力が非連結です。"); (time, ord, parent, head) } fn dfs(x: usize, p: usize, g: &mut [Vec]) -> usize { let mut child = g[x].iter().copied().filter(|&y| y != p).collect::>(); let mut size = 1; let mut max_size = 1; for i in 0..child.len() { let s = dfs(child[i], x, g); if max_size < s { max_size = s; child.swap(0, i); } size += s; } g[x] = child; size } fn efs( x: usize, g: &[Vec], time: &mut [usize], ord: &mut Vec, parent: &mut [usize], head: &mut [usize], ) { time[x] = ord.len(); ord.push(x); if !g[x].is_empty() { let h = g[x][0]; head[h] = head[x]; parent[h] = x; efs(h, g, time, ord, parent, head); for &y in &g[x][1..] { head[y] = y; parent[y] = x; efs(y, g, time, ord, parent, head); } } } } // }}} // fp {{{ #[allow(dead_code)] mod fp { use std::{ cmp::PartialEq, fmt, hash::{Hash, Hasher}, iter::{successors, Product, Sum}, marker::PhantomData, mem::swap, ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign}, }; pub trait Mod: Clone + Copy + Hash { const P: u32; const K: u32; const R2: u32 = ((1_u128 << 64) % Self::P as u128) as _; // 2 ^ 64 mod P } fn reduce(x: u64) -> u32 { ((x + u64::from(M::K.wrapping_mul(x as u32)) * u64::from(M::P)) >> 32) as u32 } pub fn fact_iter() -> impl Iterator> { (1..).scan(Fp::new(1), |state, x| { let ans = *state; *state *= x; Some(ans) }) } #[allow(clippy::missing_panics_doc)] pub fn fact_build(n: usize) -> [Vec>; 2] { if n == 0 { [Vec::new(), Vec::new()] } else { let fact = fact_iter::().take(n).collect::>(); let mut fact_inv = vec![fact.last().unwrap().recip(); n]; (1..n).rev().for_each(|i| fact_inv[i - 1] = fact_inv[i] * i); [fact, fact_inv] } } pub fn binom_iter() -> impl Iterator>> { successors(Some(vec![Fp::new(1)]), |last| { let mut crr = last.clone(); crr.push(Fp::new(0)); crr[1..].iter_mut().zip(last).for_each(|(x, &y)| *x += y); Some(crr) }) } #[macro_export] macro_rules! define_mod { ($(($Fp: ident, $Mod: ident, $mod: expr, $k: expr),)*) => {$( #[derive(Clone, Debug, Default, Hash, Copy)] pub struct $Mod {} impl Mod for $Mod { const P: u32 = $mod; const K: u32 = $k; } pub type $Fp = Fp<$Mod>; )*} } define_mod! { (F998244353, Mod998244353, 998_244_353, 998_244_351), (F1000000007, Mod1000000007, 1_000_000_007, 2_226_617_417), (F1012924417, Mod1012924417, 1_012_924_417, 1_012_924_415), (F924844033, Mod924844033, 924_844_033, 924_844_031), } #[derive(Clone, Default, Copy)] pub struct Fp { value: u32, __marker: PhantomData, } impl Fp { pub const P: u32 = M::P; pub fn new(value: u32) -> Self { Self::from_raw(reduce::(u64::from(value) * u64::from(M::R2))) } pub fn value(self) -> u32 { let x = reduce::(u64::from(self.value)); if M::P <= x { x - M::P } else { x } } #[allow(clippy::many_single_char_names)] pub fn recip(self) -> Self { assert_ne!(self, Self::new(0), "0 はだめ。"); let mut x = M::P as i32; let mut y = self.value() as i32; let mut u = 0; let mut v = 1; while y != 0 { let q = x / y; x -= q * y; u -= q * v; swap(&mut x, &mut y); swap(&mut u, &mut v); } debug_assert_eq!(x, 1); if u < 0 { debug_assert_eq!(v, M::P as i32); u += v; } Self::new(u as u32) } pub fn pow>(self, exp: T) -> Self { let mut exp = exp.into(); if exp == 0 { return Self::new(1); } let mut base = self; let mut acc = Self::new(1); while 1 < exp { if exp & 1 == 1 { acc *= base; } exp /= 2; base *= base; } acc * base } fn from_raw(value: u32) -> Self { Self { value, __marker: PhantomData, } } } fn simplify(value: i32, p: i32) -> (i32, i32, i32) { if value.abs() < 10_000 { (value, 1, 0) } else { let mut q = p.div_euclid(value); let mut r = p.rem_euclid(value); if value <= 2 * r { q += 1; r -= value; } let (num, pden, ppden) = simplify(r, value); let den = ppden - q * pden; (num, den, pden) } } macro_rules! impl_from_large_int { ($($T: ty), *$(,)?) => {$( impl From<$T> for Fp { fn from(x: $T) -> Self { Self::new(x.rem_euclid(M::P as _) as u32) } } )*} } impl_from_large_int! { u32, u64, u128, usize, i32, i64, i128, isize, } macro_rules! impl_from_small_int { ($($T: ty), *$(,)?) => {$( impl From<$T> for Fp { fn from(x: $T) -> Self { Self::new(x as u32) } } )*} } impl_from_small_int! { u8, u16, i8, i16, } impl PartialEq for Fp { fn eq(&self, other: &Self) -> bool { fn value(fp: Fp) -> u32 { if fp.value >= M::P { fp.value - M::P } else { fp.value } } value(*self) == value(*other) } } impl Eq for Fp {} impl Hash for Fp { fn hash(&self, state: &mut H) { self.value().hash(state); } } impl> AddAssign for Fp { fn add_assign(&mut self, rhs: T) { self.value += rhs.into().value; if M::P * 2 <= self.value { self.value -= M::P * 2; } } } impl> SubAssign for Fp { fn sub_assign(&mut self, rhs: T) { let rhs = rhs.into(); if self.value < rhs.value { self.value += M::P * 2; } self.value -= rhs.value; } } impl> MulAssign for Fp { fn mul_assign(&mut self, rhs: T) { self.value = reduce::(u64::from(self.value) * u64::from(rhs.into().value)); } } #[allow(clippy::suspicious_op_assign_impl)] impl> DivAssign for Fp { fn div_assign(&mut self, rhs: T) { *self *= rhs.into().recip(); } } impl<'a, M: Mod> From<&'a Self> for Fp { fn from(x: &Self) -> Self { *x } } macro_rules! forward_ops { ($(($trait:ident, $method_assign:ident, $method:ident),)*) => {$( impl>> $trait for Fp { type Output = Self; fn $method(mut self, rhs: T) -> Self { self.$method_assign(rhs); self } } impl<'a, M: Mod, T: Into>> $trait for &'a Fp { type Output = Fp; fn $method(self, other: T) -> Self::Output { $trait::$method(*self, other) } } )*}; } forward_ops! { (Add, add_assign, add), (Sub, sub_assign, sub), (Mul, mul_assign, mul), (Div, div_assign, div), } impl Neg for Fp { type Output = Self; fn neg(self) -> Self { Self::from_raw(M::P * 2 - self.value) } } impl Sum for Fp { fn sum>(iter: I) -> Self { iter.fold(Self::new(0), |b, x| b + x) } } impl Product for Fp { fn product>(iter: I) -> Self { iter.fold(Self::new(1), |b, x| b * x) } } impl<'a, M: Mod> Sum<&'a Self> for Fp { fn sum>(iter: I) -> Self { iter.fold(Self::new(0), |b, x| b + x) } } impl<'a, M: Mod> Product<&'a Self> for Fp { fn product>(iter: I) -> Self { iter.fold(Self::new(1), |b, x| b * x) } } impl fmt::Debug for Fp { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { let (num, den, _) = simplify(self.value() as i32, M::P as i32); let (num, den) = match den.signum() { 1 => (num, den), -1 => (-num, -den), _ => unreachable!(), }; if den == 1 { write!(f, "{}", num) } else { write!(f, "{}/{}", num, den) } } } impl fmt::Display for Fp { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.value().fmt(f) } } } // }}} // segtree {{{ #[allow(dead_code)] mod segtree { use std::{ fmt::{self, Debug, Formatter}, ops::{Bound, Deref, DerefMut, Drop, Index, Range, RangeBounds}, slice::SliceIndex, }; pub struct Segtree { len: usize, table: Box<[T]>, op: Op, identity: Ideneity, } impl Segtree where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { pub fn new(slice: &[T], op: Op, identity: Identity) -> Self { let len = slice.len(); let mut table = slice.to_vec(); table.extend(slice.iter().cloned()); let mut table = table.into_boxed_slice(); (1..len) .rev() .for_each(|i| table[i] = op(table[2 * i].clone(), table[2 * i + 1].clone())); Self { len, table, op, identity, } } pub fn as_slice(&self) -> &[T] { &self.table[self.len..] } pub fn entry(&mut self, index: usize) -> Entry<'_, T, Op, Identity> { Entry { seg: self, index } } pub fn fold(&self, range: impl RangeBounds) -> T { let Range { mut start, mut end } = open(range, self.len); start += self.len; end += self.len; let mut fl = (self.identity)(); let mut fr = (self.identity)(); while start != end { if start % 2 == 1 { fl = (self.op)(fl, self.table[start].clone()); start += 1; } if end % 2 == 1 { end -= 1; fr = (self.op)(self.table[end].clone(), fr); } start /= 2; end /= 2; } (self.op)(fl, fr) } pub fn search_forward( &self, range: impl RangeBounds, mut pred: impl FnMut(&T) -> bool, ) -> usize { let Range { mut start, mut end } = open(range, self.len); if start == end { start } else { start += self.len; end += self.len; let orig_end = end; let mut crr = (self.identity)(); let mut shift = 0; while start != end { if start % 2 == 1 { let nxt = (self.op)(crr.clone(), self.table[start].clone()); if !pred(&nxt) { return self.search_subtree_forward(crr, start, pred); } crr = nxt; start += 1; } start >>= 1; end >>= 1; shift += 1; } for p in (0..shift).rev() { let end = (orig_end >> p) - 1; if end % 2 == 0 { let nxt = (self.op)(crr.clone(), self.table[end].clone()); if !pred(&nxt) { return self.search_subtree_forward(crr, end, pred); } crr = nxt; } } orig_end - self.len } } pub fn search_backward( &self, range: impl RangeBounds, mut pred: impl FnMut(&T) -> bool, ) -> usize { let Range { mut start, mut end } = open(range, self.len); if start == end { start } else { start += self.len; end += self.len; let orig_start_m1 = start - 1; let mut crr = (self.identity)(); let mut shift = 0; while start != end { if end % 2 == 1 { end -= 1; let nxt = (self.op)(self.table[end].clone(), crr.clone()); if !pred(&nxt) { return self.search_subtree_backward(crr, end, pred); } crr = nxt; } start = (start + 1) >> 1; end >>= 1; shift += 1; } for p in (0..shift).rev() { let start = (orig_start_m1 >> p) + 1; if start % 2 == 1 { let nxt = (self.op)(self.table[start].clone(), crr.clone()); if !pred(&nxt) { return self.search_subtree_backward(crr, start, pred); } crr = nxt; } } orig_start_m1 + 1 - self.len } } fn search_subtree_forward( &self, mut crr: T, mut root: usize, mut pred: impl FnMut(&T) -> bool, ) -> usize { while root < self.len { let nxt = (self.op)(crr.clone(), self.table[root * 2].clone()); root = if pred(&nxt) { crr = nxt; root * 2 + 1 } else { root * 2 }; } root - self.len } fn search_subtree_backward( &self, mut crr: T, mut root: usize, mut pred: impl FnMut(&T) -> bool, ) -> usize { while root < self.len { let nxt = (self.op)(self.table[root * 2 + 1].clone(), crr.clone()); root = if pred(&nxt) { crr = nxt; root * 2 } else { root * 2 + 1 }; } root + 1 - self.len } } fn open(range: impl RangeBounds, len: usize) -> Range { (match range.start_bound() { Bound::Unbounded => 0, Bound::Included(&x) => x, Bound::Excluded(&x) => x + 1, })..match range.end_bound() { Bound::Excluded(&x) => x, Bound::Included(&x) => x + 1, Bound::Unbounded => len, } } impl Debug for Segtree where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { fn fmt(&self, w: &mut Formatter<'_>) -> fmt::Result { w.debug_tuple("Segtree") .field(&&self.table[self.len..]) .finish() } } impl, T, Op, Identity> Index for Segtree where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { type Output = I::Output; fn index(&self, index: I) -> &I::Output { &self.as_slice()[index] } } pub struct Entry<'a, T, Op, Identity> where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { seg: &'a mut Segtree, index: usize, } impl<'a, T, Op, Identity> Drop for Entry<'a, T, Op, Identity> where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { fn drop(&mut self) { let mut index = self.index + self.seg.len; while index != 0 { index /= 2; self.seg.table[index] = (self.seg.op)( self.seg.table[index * 2].clone(), self.seg.table[index * 2 + 1].clone(), ); } } } impl<'a, T, Op, Identity> Deref for Entry<'a, T, Op, Identity> where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { type Target = T; fn deref(&self) -> &Self::Target { &self.seg[self.index] } } impl<'a, T, Op, Identity> DerefMut for Entry<'a, T, Op, Identity> where T: Clone, Op: Fn(T, T) -> T, Identity: Fn() -> T, { fn deref_mut(&mut self) -> &mut Self::Target { let index = self.index; let len = self.seg.len; &mut (self.seg.table[len..])[index] } } } // }}} // union_find {{{ #[allow(dead_code)] mod union_find { use std::{ cell::RefCell, fmt::{Debug, Formatter, Result}, mem::swap, }; #[derive(Clone)] pub struct UnionFind(RefCell>); impl UnionFind { pub fn new(len: usize) -> Self { Self(RefCell::new(vec![-1; len])) } pub fn is_empty(&self) -> bool { self.0.borrow().is_empty() } pub fn len(&self) -> usize { self.0.borrow().len() } pub fn push(&mut self) { self.0.borrow_mut().push(-1); } pub fn find(&self, i: usize) -> usize { self.find_and_size(i)[0] } pub fn size(&self, i: usize) -> usize { self.find_and_size(i)[1] } pub fn union(&mut self, u: usize, v: usize) { let [mut u, su] = self.find_and_size(u); let [mut v, sv] = self.find_and_size(v); if u == v { return; } if su > sv { swap(&mut u, &mut v); } let mut table = self.0.borrow_mut(); table[v] = -((su + sv) as isize); table[u] = v as isize; } pub fn same(&self, u: usize, v: usize) -> bool { self.find(u) == self.find(v) } pub fn is_root(&self, u: usize) -> bool { self.find(u) == u } fn find_and_size(&self, mut x: usize) -> [usize; 2] { assert!(x < self.0.borrow().len()); let mut child = Vec::new(); loop { let elm = self.0.borrow()[x]; x = match elm { p if 0 <= p => p as usize, elm => { let sz = (-elm) as usize; let mut table = self.0.borrow_mut(); child .iter() .copied() .filter(|&y| x != y) .for_each(|y| table[y] = x as isize); return [x, sz]; } }; child.push(x); } } } impl Debug for UnionFind { fn fmt(&self, f: &mut Formatter<'_>) -> Result { use std::collections::HashMap; let mut map = HashMap::new(); for i in 0..self.len() { map.entry(self.find(i)).or_insert_with(Vec::new).push(i); } f.debug_list().entries(map.values()).finish() } } } // }}} // ngtio {{{ #[allow(dead_code)] mod ngtio { mod i { use std::{ io::{self, BufRead}, iter, }; pub use self::{ multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen}, token::{Token, Usize1}, }; pub fn with_stdin() -> Tokenizer> { io::BufReader::new(io::stdin()).tokenizer() } pub fn with_str(src: &str) -> Tokenizer<&[u8]> { src.as_bytes().tokenizer() } pub struct Tokenizer { queue: Vec, // FIXME: String のみにすると速そうです。 scanner: S, } macro_rules! prim_method { ($name:ident: $T:ty) => { pub fn $name(&mut self) -> $T { <$T>::leaf().parse(self) } }; ($name:ident) => { prim_method!($name: $name); }; } macro_rules! prim_methods { ($name:ident: $T:ty; $($rest:tt)*) => { prim_method!($name:$T); prim_methods!($($rest)*); }; ($name:ident; $($rest:tt)*) => { prim_method!($name); prim_methods!($($rest)*); }; () => () } impl Tokenizer { pub fn token(&mut self) -> String { self.load(); self.queue.pop().expect("入力が終了したのですが。") } pub fn new(scanner: S) -> Self { Self { queue: Vec::new(), scanner, } } fn load(&mut self) { while self.queue.is_empty() { let mut s = String::new(); let length = self.scanner.read_line(&mut s).unwrap(); // 入力が UTF-8 でないときにエラーだそうです。 if length == 0 { break; } self.queue = s.split_whitespace().rev().map(str::to_owned).collect(); } } pub fn skip_line(&mut self) { assert!( self.queue.is_empty(), "行の途中で呼ばないでいただきたいです。現在のトークンキュー: {:?}", &self.queue ); self.load(); } pub fn end(&mut self) { self.load(); assert!(self.queue.is_empty(), "入力はまだあります!"); } pub fn parse(&mut self) -> T::Output { T::parse(&self.token()) } pub fn parse_collect(&mut self, n: usize) -> B where B: iter::FromIterator, { iter::repeat_with(|| self.parse::()).take(n).collect() } pub fn tuple(&mut self) -> ::Output { T::leaf_tuple().parse(self) } pub fn vec(&mut self, len: usize) -> Vec { T::leaf().vec(len).parse(self) } pub fn vec_tuple( &mut self, len: usize, ) -> Vec<::Output> { T::leaf_tuple().vec(len).parse(self) } pub fn vec2(&mut self, height: usize, width: usize) -> Vec> { T::leaf().vec(width).vec(height).parse(self) } pub fn vec2_tuple( &mut self, height: usize, width: usize, ) -> Vec::Output>> where T: RawTuple, { T::leaf_tuple().vec(width).vec(height).parse(self) } prim_methods! { u8; u16; u32; u64; u128; usize; i8; i16; i32; i64; i128; isize; f32; f64; char; string: String; } } mod token { use super::multi_token::Leaf; use std::{any, fmt, marker, str}; pub trait Token: Sized { type Output; fn parse(s: &str) -> Self::Output; fn leaf() -> Leaf { Leaf(marker::PhantomData) } } impl Token for T where T: str::FromStr, ::Err: fmt::Debug, { type Output = Self; fn parse(s: &str) -> Self::Output { s.parse().unwrap_or_else(|_| { panic!("Parse error!: ({}: {})", s, any::type_name::(),) }) } } pub struct Usize1 {} impl Token for Usize1 { type Output = usize; fn parse(s: &str) -> Self::Output { usize::parse(s) .checked_sub(1) .expect("Parse error! (Zero substruction error of Usize1)") } } } mod multi_token { use super::{Token, Tokenizer}; use std::{io::BufRead, iter, marker}; pub trait Parser: Sized { type Output; fn parse(&self, server: &mut Tokenizer) -> Self::Output; fn vec(self, len: usize) -> VecLen { VecLen { len, elem: self } } } pub struct Leaf(pub(super) marker::PhantomData); impl Parser for Leaf { type Output = T::Output; fn parse(&self, server: &mut Tokenizer) -> T::Output { server.parse::() } } pub struct VecLen { pub len: usize, pub elem: T, } impl Parser for VecLen { type Output = Vec; fn parse(&self, server: &mut Tokenizer) -> Self::Output { iter::repeat_with(|| self.elem.parse(server)) .take(self.len) .collect() } } pub trait RawTuple { type LeafTuple: Parser; fn leaf_tuple() -> Self::LeafTuple; } pub trait ParserTuple { type Tuple: Parser; fn tuple(self) -> Self::Tuple; } pub struct Tuple(pub T); macro_rules! impl_tuple { ($($t:ident: $T:ident),*) => { impl<$($T),*> Parser for Tuple<($($T,)*)> where $($T: Parser,)* { type Output = ($($T::Output,)*); #[allow(unused_variables)] fn parse(&self, server: &mut Tokenizer) -> Self::Output { match self { Tuple(($($t,)*)) => { ($($t.parse(server),)*) } } } } impl<$($T: Token),*> RawTuple for ($($T,)*) { type LeafTuple = Tuple<($(Leaf<$T>,)*)>; fn leaf_tuple() -> Self::LeafTuple { Tuple(($($T::leaf(),)*)) } } impl<$($T: Parser),*> ParserTuple for ($($T,)*) { type Tuple = Tuple<($($T,)*)>; fn tuple(self) -> Self::Tuple { Tuple(self) } } }; } impl_tuple!(); impl_tuple!(t1: T1); impl_tuple!(t1: T1, t2: T2); impl_tuple!(t1: T1, t2: T2, t3: T3); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7); impl_tuple!( t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7, t8: T8 ); } trait Scanner: BufRead + Sized { fn tokenizer(self) -> Tokenizer { Tokenizer::new(self) } } impl Scanner for R {} } pub use self::i::{with_stdin, with_str}; pub mod prelude { pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1}; } } // }}}