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::<Vec<_>>();
    let q = buf.usize();
    let queries = repeat_with(|| ([buf.usize() - 1, buf.usize() - 1], buf.usize() - 1))
        .take(q)
        .collect::<Vec<_>>();

    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<Option<Fp>> {
    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::<Vec<_>>(),
        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::<Fp>()
                            + avoid_cost
                            + hld
                                .iter_e(avoid_v1, end_v1)
                                .map(|(l, r)| seg_time_to_weight.fold(l..=r))
                                .sum::<Fp>()
                    } else {
                        hld.iter_e(end_v0, avoid_v1)
                            .map(|(l, r)| seg_time_to_weight.fold(l..=r))
                            .sum::<Fp>()
                            + avoid_cost
                            + hld
                                .iter_e(avoid_v0, end_v1)
                                .map(|(l, r)| seg_time_to_weight.fold(l..=r))
                                .sum::<Fp>()
                    }
                })
            } else {
                // 回避不要な場合
                Some(
                    hld.iter_e(end_v0, end_v1)
                        .map(|(l, r)| seg_time_to_weight.fold(l..=r))
                        .sum::<Fp>(),
                )
            }
        })
        .collect::<Vec<_>>()
}

#[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::<Vec<_>>();

            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::<Vec<_>>();
        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<Option<Fp>> {
        let edges = edges
            .into_iter()
            .enumerate()
            .map(|(i, &[u, v])| ([u, v], 2u64.pow(i as u32 + 1)))
            .collect::<Vec<_>>();
        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::<Vec<_>>()
    }

    fn remove_item<T, V>(me: &mut Vec<T>, item: &V) -> Option<T>
    where
        T: PartialEq<V>,
    {
        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>]) -> ([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<usize>]) -> (Vec<usize>, 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<usize>]) -> Vec<u32> {
            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<usize>]) -> (Vec<u32>, Vec<usize>) {
            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<usize>]) -> Option<Vec<usize>> {
            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<Vec<usize>> {
            make_undirected_by(n, edges, |&(u, v)| [u, v])
        }
        pub fn array_make_undirected(n: usize, edges: &[[usize; 2]]) -> Vec<Vec<usize>> {
            make_undirected_by(n, edges, |&[u, v]| [u, v])
        }
        pub fn make_undirected_by<E>(
            n: usize,
            edges: &[E],
            f: impl Fn(&E) -> [usize; 2],
        ) -> Vec<Vec<usize>> {
            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<Vec<usize>> {
            make_directed_by(n, edges, |&(u, v)| [u, v])
        }
        pub fn array_make_directed(n: usize, edges: &[[usize; 2]]) -> Vec<Vec<usize>> {
            make_directed_by(n, edges, |&[u, v]| [u, v])
        }
        pub fn make_directed_by<E>(
            n: usize,
            edges: &[E],
            f: impl Fn(&E) -> [usize; 2],
        ) -> Vec<Vec<usize>> {
            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<T: Copy>(
            n: usize,
            edges: &[(usize, usize, T)],
        ) -> Vec<Vec<(usize, T)>> {
            make_undirected_weighted_by(n, edges, |&(u, v, x)| ([u, v], x))
        }
        pub fn array_make_undirected_weighted<T: Copy>(
            n: usize,
            edges: &[([usize; 2], T)],
        ) -> Vec<Vec<(usize, T)>> {
            make_undirected_weighted_by(n, edges, |&([u, v], x)| ([u, v], x))
        }
        pub fn make_undirected_weighted_by<E, T: Copy>(
            n: usize,
            edges: &[E],
            f: impl Fn(&E) -> ([usize; 2], T),
        ) -> Vec<Vec<(usize, T)>> {
            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<T: Copy>(
            n: usize,
            edges: &[(usize, usize, T)],
        ) -> Vec<Vec<(usize, T)>> {
            make_directed_weighted_by(n, edges, |&(u, v, x)| ([u, v], x))
        }
        pub fn array_make_directed_weighted<T: Copy>(
            n: usize,
            edges: &[([usize; 2], T)],
        ) -> Vec<Vec<(usize, T)>> {
            make_directed_weighted_by(n, edges, |&([u, v], x)| ([u, v], x))
        }
        pub fn make_directed_weighted_by<E, T: Copy>(
            n: usize,
            edges: &[E],
            f: impl Fn(&E) -> ([usize; 2], T),
        ) -> Vec<Vec<(usize, T)>> {
            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<usize>,
    }
    impl UfChecklist {
        pub fn new(n: usize) -> Self {
            Self {
                uf: UnionFind::new(n + 1),
                rightmost: (0..=n).collect::<Vec<_>>(),
            }
        }
        pub fn range_check(&mut self, range: impl RangeBounds<usize>) -> 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<usize> {
            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<Self::Item> {
            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<usize>, len: usize) -> Range<usize> {
        (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::<String>()
                    )
                }
            }
            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<T, U>(table: &[U]) -> Table<'_, T, U> {
                Table {
                    _marker: PhantomData,
                    table,
                }
            }

            pub struct Table<'a, T, U> {
                table: &'a [U],
                _marker: PhantomData<T>,
            }
            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<F>(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<T>,
                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::<String>()
                            )
                        })
                }
            }
        }

        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<usize>,
        ord: Vec<usize>,
        parent: Vec<usize>,
        head: Vec<usize>,
    }
    impl Hld {
        pub fn new(root: usize, g: &mut [Vec<usize>]) -> 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::<usize>()
        }
        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<Self::Item> {
            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<Self::Item> {
            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<usize>]) -> (Vec<usize>, Vec<usize>, Vec<usize>, Vec<usize>) {
        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>]) -> usize {
        let mut child = g[x].iter().copied().filter(|&y| y != p).collect::<Vec<_>>();
        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<usize>],
        time: &mut [usize],
        ord: &mut Vec<usize>,
        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<M: Mod>(x: u64) -> u32 {
        ((x + u64::from(M::K.wrapping_mul(x as u32)) * u64::from(M::P)) >> 32) as u32
    }

    pub fn fact_iter<M: Mod>() -> impl Iterator<Item = Fp<M>> {
        (1..).scan(Fp::new(1), |state, x| {
            let ans = *state;
            *state *= x;
            Some(ans)
        })
    }

    #[allow(clippy::missing_panics_doc)]
    pub fn fact_build<M: Mod>(n: usize) -> [Vec<Fp<M>>; 2] {
        if n == 0 {
            [Vec::new(), Vec::new()]
        } else {
            let fact = fact_iter::<M>().take(n).collect::<Vec<_>>();
            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<M: Mod>() -> impl Iterator<Item = Vec<Fp<M>>> {
        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<M> {
        value: u32,
        __marker: PhantomData<M>,
    }
    impl<M: Mod> Fp<M> {
        pub const P: u32 = M::P;
        pub fn new(value: u32) -> Self {
            Self::from_raw(reduce::<M>(u64::from(value) * u64::from(M::R2)))
        }
        pub fn value(self) -> u32 {
            let x = reduce::<M>(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<T: Into<u64>>(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<M: Mod> From<$T> for Fp<M> {
                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<M: Mod> From<$T> for Fp<M> {
                fn from(x: $T) -> Self {
                    Self::new(x as u32)
                }
            }
        )*}
    }
    impl_from_small_int! {
        u8, u16,
        i8, i16,
    }

    impl<M: Mod> PartialEq for Fp<M> {
        fn eq(&self, other: &Self) -> bool {
            fn value<M: Mod>(fp: Fp<M>) -> u32 {
                if fp.value >= M::P {
                    fp.value - M::P
                } else {
                    fp.value
                }
            }
            value(*self) == value(*other)
        }
    }
    impl<M: Mod> Eq for Fp<M> {}
    impl<M: Mod> Hash for Fp<M> {
        fn hash<H: Hasher>(&self, state: &mut H) {
            self.value().hash(state);
        }
    }
    impl<M: Mod, T: Into<Self>> AddAssign<T> for Fp<M> {
        fn add_assign(&mut self, rhs: T) {
            self.value += rhs.into().value;
            if M::P * 2 <= self.value {
                self.value -= M::P * 2;
            }
        }
    }
    impl<M: Mod, T: Into<Self>> SubAssign<T> for Fp<M> {
        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<M: Mod, T: Into<Self>> MulAssign<T> for Fp<M> {
        fn mul_assign(&mut self, rhs: T) {
            self.value = reduce::<M>(u64::from(self.value) * u64::from(rhs.into().value));
        }
    }
    #[allow(clippy::suspicious_op_assign_impl)]
    impl<M: Mod, T: Into<Self>> DivAssign<T> for Fp<M> {
        fn div_assign(&mut self, rhs: T) {
            *self *= rhs.into().recip();
        }
    }

    impl<'a, M: Mod> From<&'a Self> for Fp<M> {
        fn from(x: &Self) -> Self {
            *x
        }
    }

    macro_rules! forward_ops {
        ($(($trait:ident, $method_assign:ident, $method:ident),)*) => {$(
            impl<M: Mod, T: Into<Fp<M>>> $trait<T> for Fp<M> {
                type Output = Self;
                fn $method(mut self, rhs: T) -> Self {
                    self.$method_assign(rhs);
                    self
                }
            }
            impl<'a, M: Mod, T: Into<Fp<M>>> $trait<T> for &'a Fp<M> {
                type Output = Fp<M>;
                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<M: Mod> Neg for Fp<M> {
        type Output = Self;
        fn neg(self) -> Self {
            Self::from_raw(M::P * 2 - self.value)
        }
    }
    impl<M: Mod> Sum for Fp<M> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::new(0), |b, x| b + x)
        }
    }
    impl<M: Mod> Product for Fp<M> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::new(1), |b, x| b * x)
        }
    }
    impl<'a, M: Mod> Sum<&'a Self> for Fp<M> {
        fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::new(0), |b, x| b + x)
        }
    }
    impl<'a, M: Mod> Product<&'a Self> for Fp<M> {
        fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::new(1), |b, x| b * x)
        }
    }
    impl<M: Mod> fmt::Debug for Fp<M> {
        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<M: Mod> fmt::Display for Fp<M> {
        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<T, Op, Ideneity> {
        len: usize,
        table: Box<[T]>,
        op: Op,
        identity: Ideneity,
    }
    impl<T, Op, Identity> Segtree<T, Op, Identity>
    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<usize>) -> 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<usize>,
            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<usize>,
            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<usize>, len: usize) -> Range<usize> {
        (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<T: Debug, Op, Identity> Debug for Segtree<T, Op, Identity>
    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<I: SliceIndex<[T]>, T, Op, Identity> Index<I> for Segtree<T, Op, Identity>
    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<T, Op, Identity>,
        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<Vec<isize>>);
    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<io::Stdin>> {
            io::BufReader::new(io::stdin()).tokenizer()
        }

        pub fn with_str(src: &str) -> Tokenizer<&[u8]> {
            src.as_bytes().tokenizer()
        }

        pub struct Tokenizer<S: BufRead> {
            queue: Vec<String>, // 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<S: BufRead> Tokenizer<S> {
            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<T: Token>(&mut self) -> T::Output {
                T::parse(&self.token())
            }

            pub fn parse_collect<T: Token, B>(&mut self, n: usize) -> B
            where
                B: iter::FromIterator<T::Output>,
            {
                iter::repeat_with(|| self.parse::<T>()).take(n).collect()
            }

            pub fn tuple<T: RawTuple>(&mut self) -> <T::LeafTuple as Parser>::Output {
                T::leaf_tuple().parse(self)
            }

            pub fn vec<T: Token>(&mut self, len: usize) -> Vec<T::Output> {
                T::leaf().vec(len).parse(self)
            }

            pub fn vec_tuple<T: RawTuple>(
                &mut self,
                len: usize,
            ) -> Vec<<T::LeafTuple as Parser>::Output> {
                T::leaf_tuple().vec(len).parse(self)
            }

            pub fn vec2<T: Token>(&mut self, height: usize, width: usize) -> Vec<Vec<T::Output>> {
                T::leaf().vec(width).vec(height).parse(self)
            }

            pub fn vec2_tuple<T>(
                &mut self,
                height: usize,
                width: usize,
            ) -> Vec<Vec<<T::LeafTuple as Parser>::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<Self> {
                    Leaf(marker::PhantomData)
                }
            }

            impl<T> Token for T
            where
                T: str::FromStr,
                <Self as 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::<Self>(),)
                    })
                }
            }

            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<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output;
                fn vec(self, len: usize) -> VecLen<Self> {
                    VecLen { len, elem: self }
                }
            }
            pub struct Leaf<T>(pub(super) marker::PhantomData<T>);
            impl<T: Token> Parser for Leaf<T> {
                type Output = T::Output;
                fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> T::Output {
                    server.parse::<T>()
                }
            }

            pub struct VecLen<T> {
                pub len: usize,
                pub elem: T,
            }
            impl<T: Parser> Parser for VecLen<T> {
                type Output = Vec<T::Output>;
                fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> 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<T>(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<S: BufRead >(&self, server: &mut Tokenizer<S>) -> 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<Self> {
                Tokenizer::new(self)
            }
        }
        impl<R: BufRead> Scanner for R {}
    }

    pub use self::i::{with_stdin, with_str};

    pub mod prelude {
        pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1};
    }
}
// }}}