#define PROBLEM "https://yukicoder.me/problems/no/1326" 

#ifndef GRAPH_GRAPH_TEMPLATE_HPP
#define GRAPH_GRAPH_TEMPLATE_HPP 1

#include <cassert>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>

#ifndef TYPE_TRAITS_HPP
#define TYPE_TRAITS_HPP 1


#include <istream>
#include <ostream>
#include <type_traits>

namespace kk2 {

template <typename T>
using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value
                                                       or std::is_same<T, __int128>::value,
                                                   std::true_type,
                                                   std::false_type>::type;

template <typename T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value
                                  or std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using is_integral =
    typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
                                  or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
                                            std::true_type,
                                            std::false_type>::type;

template <typename T>
using is_unsigned =
    typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;

template <typename T>
using to_unsigned =
    typename std::conditional<is_signed_int128<T>::value,
                              make_unsigned_int128<T>,
                              typename std::conditional<std::is_signed<T>::value,
                                                        std::make_unsigned<T>,
                                                        std::common_type<T>>::type>::type;

template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;


template <typename T>
using is_function_pointer =
    typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,
                              std::true_type,
                              std::false_type>::type;

template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>
struct is_two_args_function_pointer : std::false_type {};

template <typename R, typename T1, typename T2>
struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};

template <typename T>
using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;


namespace type_traits {

struct istream_tag {};

struct ostream_tag {};

} // namespace type_traits

template <typename T>
using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value
                                                          || std::is_same<T, std::ifstream>::value,
                                                      std::true_type,
                                                      std::false_type>::type;
template <typename T>
using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value
                                                          || std::is_same<T, std::ofstream>::value,
                                                      std::true_type,
                                                      std::false_type>::type;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;

template <typename T>
using is_istream =
    typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using is_ostream =
    typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;


} // namespace kk2

#endif // TYPE_TRAITS_HPP

// #include "../type_traits/type_traits.hpp"

namespace kk2 {

namespace graph {

struct empty {};

template <class T> struct _Edge {
    int from, to, id;
    T cost;

    _Edge(int to_, T cost_, int from_ = -1, int id_ = -1)
        : from(from_),
          to(to_),
          id(id_),
          cost(cost_) {}

    _Edge() : from(-1), to(-1), id(-1), cost() {}

    operator int() const { return to; }

    _Edge rev() const { return _Edge(from, cost, to, id); }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const _Edge &e) {
        if constexpr (std::is_same_v<T, empty>) return os << e.from << " -> " << e.to;
        else return os << e.from << " -> " << e.to << " : " << e.cost;
    }
};
template <class T> using _Edges = std::vector<_Edge<T>>;

template <class T, bool is_directed> struct AdjacencyList : std::vector<_Edges<T>> {
    using value_type = T;
    using edge_type = _Edge<T>;

    using directed = std::integral_constant<bool, is_directed>;
    using weighted = std::integral_constant<bool, !std::is_same_v<T, empty>>;
    using adjacency_list = std::integral_constant<bool, true>;
    using adjacency_matrix = std::integral_constant<bool, false>;

    AdjacencyList() = default;

    AdjacencyList(int n_) : std::vector<_Edges<T>>(n_) {}

    // input を使うことが前提
    AdjacencyList(int n_, int m_) : std::vector<_Edges<T>>(n_), edges(m_) {}

    AdjacencyList(int n_, const _Edges<T> &edges_) : std::vector<_Edges<T>>(n_), edges(edges_) {
        for (auto &&e : edges) {
            (*this)[e.from].emplace_back(e);
            if constexpr (!is_directed) (*this)[e.to].emplace_back(e.rev());
        }
    }

    _Edges<T> edges;

    int num_vertices() const { return (int)this->size(); }

    int num_edges() const { return (int)edges.size(); }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    AdjacencyList &input(IStream &is, bool oneindexed = false) {
        for (int i = 0; i < num_edges(); i++) {
            int u, v;
            T w{};
            is >> u >> v;
            if constexpr (!std::is_same_v<T, empty>) is >> w;
            if (oneindexed) --u, --v;
            _add_edge<true>(u, v, w, i);
        }
        return *this;
    }

    void edge_clear() {
        for (auto &v : *this) v.clear();
        edges.clear();
    }

    void add_edge(int from, int to, T cost = T{}) { _add_edge<false>(from, to, cost, num_edges()); }

  private:
    template <bool update = false>
    void _add_edge(int from, int to, T cost, int id) {
        (*this)[from].emplace_back(to, cost, from, id);
        if constexpr (!is_directed) (*this)[to].emplace_back(from, cost, to, id);
        if constexpr (update) edges[id] = _Edge<T>(to, cost, from, id);
        else edges.emplace_back(to, cost, from, id);
    }
};

template <class T> struct _pair {
    T cost;
    int id;

    _pair(T cost_, int id_) : cost(cost_), id(id_) {}

    _pair() : cost(), id(-1) {}

    operator bool() const { return id != -1; }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const _pair &p) {
        if constexpr (std::is_same_v<T, empty>) return os;
        else return os << p.cost;
    }
};
template <class T> using _pairs = std::vector<_pair<T>>;

template <class T, bool is_directed> struct AdjacencyMatrix : std::vector<_pairs<T>> {
    using value_type = T;
    using edge_type = _pair<T>;

    using directed = std::integral_constant<bool, is_directed>;
    using weighted = std::integral_constant<bool, !std::is_same_v<T, empty>>;
    using adjacency_list = std::integral_constant<bool, false>;
    using adjacency_matrix = std::integral_constant<bool, true>;

    AdjacencyMatrix() = default;

    AdjacencyMatrix(int n_) : std::vector<_pairs<T>>(n_, _pairs<T>(n_)) {}

    // input を使うことが前提
    AdjacencyMatrix(int n_, int m_) : std::vector<_pairs<T>>(n_, _pairs<T>(n_)), edges(m_) {}

    AdjacencyMatrix(int n_, const _Edges<T> &edges_)
        : std::vector<_pairs<T>>(n_, _pairs<T>(n_)),
          edges(edges_) {
        for (auto &&e : edges) {
            (*this)[e.from][e.to] = _pair<T>(e.cost, e.id);
            if constexpr (!is_directed) (*this)[e.to][e.from] = _pair<T>(e.cost, e.id);
        }
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    AdjacencyMatrix &input(IStream &is, bool oneindexed = false) {
        for (int i = 0; i < num_edges(); i++) {
            int u, v;
            T w{};
            is >> u >> v;
            if constexpr (!std::is_same_v<T, empty>) is >> w;
            if (oneindexed) --u, --v;
            _add_edge<true>(u, v, w, i);
        }
        return *this;
    }

    _Edges<T> edges;

    int num_vertices() const { return (int)this->size(); }

    int num_edges() const { return (int)edges.size(); }

    void edge_clear() {
        for (auto &&e : edges) {
            (*this)[e.from][e.to] = _pair<T>(e.cost, e.id);
            if constexpr (!is_directed) (*this)[e.to][e.from] = _pair<T>(e.cost, e.id);
        }
        edges.clear();
    }

    void add_edge(int from, int to, T cost = T{}) { _add_edge<false>(from, to, cost, num_edges()); }

  private:
    template <bool update = false>
    void _add_edge(int from, int to, T cost, int id) {
        (*this)[from][to] = _pair<T>(cost, id);
        if constexpr (!is_directed) (*this)[to][from] = _pair<T>(cost, id);
        if constexpr (update) edges[id] = _Edge<T>(to, cost, from, id);
        else edges.emplace_back(to, cost, from, id);
    }
};

template <class G>
G reverse(const G &g) {
    G res(g.num_vertices());
    for (auto &&e : g.edges) res.add_edge(e.to, e.from, e.cost);
    return res;
}

template <class T, class IStream, is_istream_t<IStream> * = nullptr>
_Edges<T> &input(IStream &is, _Edges<T>& edges, bool is_one_indexed) {
    for (int i = 0; i < (int)edges.size(); i++) {
        int u, v;
        T w{};
        is >> u >> v;
        if (is_one_indexed) --u, --v;
        if constexpr (!std::is_same_v<T, empty>) is >> w;
        edges[i] = _Edge<T>(v, w, u, i);
    }
    return edges;
}

template <class T, std::enable_if_t<std::is_same_v<T, empty>> * = nullptr>
void add_edge(_Edges<T> &edges, int from, int to) {
    edges.emplace_back(to, empty{}, from, (int)edges.size());
}

template <class T, std::enable_if_t<!std::is_same_v<T, empty>> * = nullptr>
void add_edge(_Edges<T> &edges, int from, int to, T cost) {
    edges.emplace_back(to, cost, from, (int)edges.size());
}

} // namespace graph

template <typename T> using WAdjList = graph::AdjacencyList<T, false>;
template <typename T> using DWAdjList = graph::AdjacencyList<T, true>;
using AdjList = graph::AdjacencyList<graph::empty, false>;
using DAdjList = graph::AdjacencyList<graph::empty, true>;

template <typename T> using WAdjMat = graph::AdjacencyMatrix<T, false>;
template <typename T> using DWAdjMat = graph::AdjacencyMatrix<T, true>;
using AdjMat = graph::AdjacencyMatrix<graph::empty, false>;
using DAdjMat = graph::AdjacencyMatrix<graph::empty, true>;

template <typename T> using WEdge = graph::_Edge<T>;
template <typename T> using WEdges = graph::_Edges<T>;
using Edge = graph::_Edge<graph::empty>;
using Edges = graph::_Edges<graph::empty>;
using graph::input;
using graph::reverse;
using graph::add_edge;

} // namespace kk2

#endif // GRAPH_GRAPH_TEMPLATE_HPP

// #include "../../graph/graph.hpp"
#ifndef GRAPH_TREE_BLOCK_CUT_TREE_HPP
#define GRAPH_TREE_BLOCK_CUT_TREE_HPP 1

#include <vector>

#ifndef GRAPH_BCC_HPP
#define GRAPH_BCC_HPP 1

#include <functional>
#include <vector>

#ifndef GRAPH_LOWLINK_HPP
#define GRAPH_LOWLINK_HPP 1

#include <algorithm>
#include <cassert>
#include <functional>
#include <type_traits>
#include <vector>

namespace kk2 {

template <class G> struct LowLink {
    static_assert(!G::directed::value, "LowLink requires undirected graph");

    int n, m;
    const G &g;
    std::vector<int> ord, low;
    std::vector<bool> root, used_on_dfs_tree;
    std::vector<int> bridges, articulations;

    LowLink(const G &g_)
        : n(g_.num_vertices()),
          m(g_.num_edges()),
          g(g_),
          ord(n, -1),
          low(n, -1),
          root(n, false),
          used_on_dfs_tree(m, false) {
        init();
    }

  private:
    // v is a child of u in DFS tree
    // edge(u, v) is a bridge <=> ord[u] < low[v]

    // u is an articulation point <=> (u is root and u has two or more children) or
    // there exists a v which is a child of u in DFS tree and ord[u] <= low[v]

    void init() {
        int k = 0;
        auto dfs = [&](auto self, int u, int ei = -1) -> int {
            low[u] = ord[u] = k++;
            bool is_articulation = false;
            int count = 0;
            for (auto &&e : g[u]) {
                if (e.id == ei) continue;
                if (ord[e.to] == -1) {
                    ++count;
                    used_on_dfs_tree[e.id] = true;
                    low[u] = std::min(low[u], self(self, e.to, e.id));
                    if (ei != -1 and ord[u] <= low[e.to]) is_articulation = true;
                    if (ord[u] < low[e.to]) bridges.emplace_back(e.id);
                }
                // back edge
                else if (ord[e.to] < ord[u]) {
                    low[u] = std::min(low[u], ord[e.to]);
                }
            }
            if (ei == -1 and count >= 2) is_articulation = true;
            if (is_articulation) articulations.emplace_back(u);
            return low[u];
        };
        for (int u = 0; u < n; u++)
            if (ord[u] == -1) {
                dfs(dfs, u);
                root[u] = true;
            }
    }
};

} // namespace kk2

#endif // GRAPH_LOWLINK_HPP

// #include "lowlink.hpp"

namespace kk2 {

template <class G> struct BCC : LowLink<G> {
    BCC(const G &g_) : LowLink<G>(g_) { init_bcc(); }

    std::vector<std::vector<int>> group_e;
    std::vector<int> comp_e;

  private:
    void init_bcc() {
        comp_e = std::vector<int>(this->m, -1);
        auto add = [&](int ei, int k) {
            group_e[k].emplace_back(ei);
            comp_e[ei] = k;
        };
        auto dfs = [&](auto self, int u, int k = -1, int ei = -1) -> void {
            for (auto &e : this->g[u]) {
                if (e.id == ei) continue;
                if (this->used_on_dfs_tree[e.id]) {
                    int nk = k;
                    if (this->low[e.to] >= this->ord[u]) nk = group_e.size(), group_e.emplace_back();
                    add(e.id, nk);
                    self(self, e.to, nk, e.id);
                }
                // back edge
                else if (this->ord[e.to] < this->ord[u]) {
                    add(e.id, k);
                }
            }
        };
        for (int u = 0; u < this->n; u++)
            if (this->root[u]) { dfs(dfs, u); }
    }

  public:
    std::vector<std::vector<int>> get_bcc_vertices() {
        std::vector<bool> buf1(this->n), buf2(this->n);
        std::vector<std::vector<int>> res;
        res.reserve(group_e.size());
        for (auto &bc : group_e) {
            if (bc.empty()) continue;
            int k = (int)res.size();
            res.emplace_back();
            for (auto &ei : bc) {
                auto e = this->g.edges[ei];
                int fr = e.from, to = e.to;
                if (!buf2[fr]) {
                    res[k].emplace_back(fr);
                    buf2[fr] = true;
                }
                if (!buf2[to]) {
                    res[k].emplace_back(to);
                    buf2[to] = true;
                }
                buf1[fr] = buf1[to] = true;
            }
            for (auto &ei : bc) {
                auto e = this->g.edges[ei];
                int fr = e.from, to = e.to;
                buf2[fr] = buf2[to] = false;
            }
        }
        for (int i = 0; i < this->n; i++)
            if (!buf1[i]) {
                int k = (int)res.size();
                res.emplace_back();
                res[k].emplace_back(i);
            }
        return res;
    }
};

} // namespace kk2

#endif // GRAPH_BCC_HPP

// #include "../bcc.hpp"

namespace kk2 {

template <class G> struct BlockCutTree : BCC<G> {
    std::vector<int> comp_v;
    std::vector<std::vector<int>> group_v;
    G forest;
    int off;

    BlockCutTree(const G &g_) : BCC<G>(g_) { init_bct(); }

    int size() const { return group_v.size(); }

    bool is_articulation(int v) const { return comp_v[v] >= off; }

  private:
    void init_bct() {
        comp_v.resize(this->n, -1);
        auto bcc_v = this->get_bcc_vertices();
        off = bcc_v.size();
        group_v.resize(bcc_v.size() + this->articulations.size());
        forest = G(group_v.size());
        for (int i = 0; i < (int)this->articulations.size(); ++i) {
            comp_v[this->articulations[i]] = i + off;
            group_v[i + off].emplace_back(this->articulations[i]);
        }

        std::vector<int> buf(this->articulations.size(), -1);

        for (int i = 0; i < (int)bcc_v.size(); ++i) {
            for (auto &v : bcc_v[i]) {
                group_v[i].emplace_back(v);
                if (comp_v[v] == -1) comp_v[v] = i;
                else if (buf[comp_v[v] - off] != i) {
                    forest.add_edge(i, comp_v[v]);
                    buf[comp_v[v] - off] = i;
                }
            }
        }
    }
};

} // namespace kk2

#endif // GRAPH_TREE_BLOCK_CUT_TREE_HPP

// #include "../../graph/tree/block_cut_tree.hpp"
#ifndef GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP
#define GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP 1

#include <cassert>
#include <functional>
#include <utility>
#include <vector>

namespace kk2 {

template <typename G> struct HeavyLightDecomposition {
    static_assert(!G::directed::value, "HeavyLightDecomposition requires undirected graph");

    G &g;
    int root, id;
    std::vector<int> sz, in, out, head, par, dep, edge_idx;

    HeavyLightDecomposition(G &g_, int root_ = 0)
        : g(g_),
          root(root_),
          id(0),
          sz(g.size(), 0),
          in(g.size(), -1),
          out(g.size(), -1),
          head(g.size(), root),
          par(g.size(), root),
          dep(g.size(), 0),
          edge_idx(g.size() - 1, -1) {
        init();
    }

    int get_edge_idx(int i) const { return edge_idx[i]; }

    std::pair<int, int> get_node_idx(int u) const { return std::make_pair(in[u], out[u]); }

    template <typename F> void path_query(int u, int v, bool is_node_query, const F &f) {
        int l = lca(u, v);
        for (auto &[a, b] : ascend(u, l)) {
            int s = a + 1, t = b;
            s > t ? f(t, s) : f(s, t);
        }
        if (is_node_query) f(in[l], in[l] + 1);
        for (auto &[a, b] : descend(l, v)) {
            int s = a, t = b + 1;
            s > t ? f(t, s) : f(s, t);
        }
    }

    template <typename F>
    void path_noncommutative_query(int u, int v, bool is_node_query, const F &f) {
        int l = lca(u, v);
        for (auto &[a, b] : ascend(u, l)) f(a + 1, b);
        if (is_node_query) f(in[l], in[l] + 1);
        for (auto &[a, b] : descend(l, v)) f(a, b + 1);
    }

    template <typename F> void subtree_query(int u, bool is_vertex_query, const F &f) {
        f(in[u] + (int)!is_vertex_query, out[u]);
    }

    int lca(int u, int v) const {
        while (head[u] != head[v]) {
            if (in[u] < in[v]) std::swap(u, v);
            u = par[head[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }

    int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }

  private:
    void init() {
        auto dfs_sz = [&](auto self, int now) -> void {
            sz[now] = 1;
            for (auto &e : g[now]) {
                if ((int)e == par[now]) {
                    if (g[now].size() >= 2 and e == g[now][0]) std::swap(e, g[now][1]);
                    else continue;
                }
                par[(int)e] = now;
                dep[(int)e] = dep[now] + 1;
                self(self, (int)e);
                sz[now] += sz[(int)e];
                if (sz[(int)e] > sz[(int)g[now][0]]) std::swap(e, g[now][0]);
            }
        };
        dfs_sz(dfs_sz, root);

        auto dfs_hld = [&](auto self, int now) -> void {
            in[now] = id++;
            for (auto &e : g[now]) {
                if ((int)e == par[now]) continue;
                head[(int)e] = ((int)e == (int)g[now][0] ? head[now] : (int)e);
                edge_idx[e.id] = id;
                self(self, (int)e);
            }
            out[now] = id;
        };
        dfs_hld(dfs_hld, root);
    }

    // [u, v)
    std::vector<std::pair<int, int>> ascend(int u, int v) const {
        std::vector<std::pair<int, int>> res;
        while (head[u] != head[v]) {
            res.emplace_back(in[u], in[head[u]]);
            u = par[head[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }

    // (u, v]
    std::vector<std::pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (head[u] == head[v]) return {std::make_pair(in[u] + 1, in[v])};
        auto res = descend(u, par[head[v]]);
        res.emplace_back(in[head[v]], in[v]);
        return res;
    }
};

} // namespace kk2

#endif // GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP

// #include "../../graph/tree/heavy_light_decomposition.hpp"
#ifndef TEMPLATE
#define TEMPLATE 1

// #pragma GCC optimize("O3,unroll-loops")

// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#ifndef TEMPLATE_FASTIO_HPP
#define TEMPLATE_FASTIO_HPP 1

#include <cctype>
#include <cstdint>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>

// #include "../type_traits/type_traits.hpp"

namespace kk2 {

namespace fastio {

struct Scanner : type_traits::istream_tag {
  private:
    static constexpr size_t INPUT_BUF = 1 << 17;
    size_t pos = 0, end = 0;
    static char buf[INPUT_BUF];
    FILE *fp;

  public:
    Scanner() : fp(stdin) {}

    Scanner(const char *file) : fp(fopen(file, "r")) {}

    ~Scanner() {
        if (fp != stdin) fclose(fp);
    }

    char now() {
        if (pos == end) {
            while (!(end = fread(buf, 1, INPUT_BUF, fp))) {}
            if (end != INPUT_BUF) buf[end] = '\0';
            pos = 0;
        }
        return buf[pos];
    }

    void skip_space() {
        while (isspace(now())) ++pos;
    }

    template <class T, is_unsigned_t<T> * = nullptr> T next_unsigned_integral() {
        skip_space();
        T res{};
        while (isdigit(now())) {
            res = res * 10 + (now() - '0');
            ++pos;
        }
        return res;
    }

    template <class T, is_signed_t<T> * = nullptr> T next_signed_integral() {
        skip_space();
        if (now() == '-') {
            ++pos;
            return T(-next_unsigned_integral<typename to_unsigned<T>::type>());
        } else return (T)next_unsigned_integral<typename to_unsigned<T>::type>();
    }

    char next_char() {
        skip_space();
        auto res = now();
        ++pos;
        return res;
    }

    std::string next_string() {
        skip_space();
        std::string res;
        while (true) {
            char c = now();
            if (isspace(c) or c == '\0') break;
            res.push_back(now());
            ++pos;
        }
        return res;
    }

    template <class T, is_unsigned_t<T> * = nullptr> Scanner &operator>>(T &x) {
        x = next_unsigned_integral<T>();
        return *this;
    }

    template <class T, is_signed_t<T> * = nullptr> Scanner &operator>>(T &x) {
        x = next_signed_integral<T>();
        return *this;
    }

    Scanner &operator>>(char &x) {
        x = next_char();
        return *this;
    }

    Scanner &operator>>(std::string &x) {
        x = next_string();
        return *this;
    }
};

struct endl_struct_t {};

struct Printer : type_traits::ostream_tag {
  private:
    static char helper[10000][5];
    static char leading_zero[10000][5];
    constexpr static size_t OUTPUT_BUF = 1 << 17;
    static char buf[OUTPUT_BUF];
    size_t pos = 0;
    FILE *fp;

    template <class T> static constexpr void div_mod(T &a, T &b, T mod) {
        a = b / mod;
        b -= a * mod;
    }

    static void init() {
        buf[0] = '\0';
        for (size_t i = 0; i < 10000; ++i) {
            leading_zero[i][0] = i / 1000 + '0';
            leading_zero[i][1] = i / 100 % 10 + '0';
            leading_zero[i][2] = i / 10 % 10 + '0';
            leading_zero[i][3] = i % 10 + '0';
            leading_zero[i][4] = '\0';

            size_t j = 0;
            if (i >= 1000) helper[i][j++] = i / 1000 + '0';
            if (i >= 100) helper[i][j++] = i / 100 % 10 + '0';
            if (i >= 10) helper[i][j++] = i / 10 % 10 + '0';
            helper[i][j++] = i % 10 + '0';
            helper[i][j] = '\0';
        }
    }

  public:
    Printer() : fp(stdout) { init(); }

    Printer(const char *file) : fp(fopen(file, "w")) { init(); }

    ~Printer() {
        write();
        if (fp != stdout) fclose(fp);
    }

    void write() {
        fwrite(buf, 1, pos, fp);
        pos = 0;
    }

    void flush() {
        write();
        fflush(fp);
    }

    void put_char(char c) {
        if (pos == OUTPUT_BUF) write();
        buf[pos++] = c;
    }

    void put_cstr(const char *s) {
        while (*s) put_char(*(s++));
    }

    void put_u32(uint32_t x) {
        uint32_t y;
        if (x >= 100000000) { // 10^8
            div_mod<uint32_t>(y, x, 100000000);
            put_cstr(helper[y]);
            div_mod<uint32_t>(y, x, 10000);
            put_cstr(leading_zero[y]);
            put_cstr(leading_zero[x]);
        } else if (x >= 10000) { // 10^4
            div_mod<uint32_t>(y, x, 10000);
            put_cstr(helper[y]);
            put_cstr(leading_zero[x]);
        } else put_cstr(helper[x]);
    }

    void put_i32(int32_t x) {
        if (x < 0) {
            put_char('-');
            put_u32(-x);
        } else put_u32(x);
    }

    void put_u64(uint64_t x) {
        uint64_t y;
        if (x >= 1000000000000ull) { // 10^12
            div_mod<uint64_t>(y, x, 1000000000000ull);
            put_u32(y);
            div_mod<uint64_t>(y, x, 100000000ull);
            put_cstr(leading_zero[y]);
            div_mod<uint64_t>(y, x, 10000ull);
            put_cstr(leading_zero[y]);
            put_cstr(leading_zero[x]);
        } else if (x >= 10000ull) { // 10^4
            div_mod<uint64_t>(y, x, 10000ull);
            put_u32(y);
            put_cstr(leading_zero[x]);
        } else put_cstr(helper[x]);
    }

    void put_i64(int64_t x) {
        if (x < 0) {
            put_char('-');
            put_u64(-x);
        } else put_u64(x);
    }

    void put_u128(__uint128_t x) {
        constexpr static __uint128_t pow10_10 = 10000000000ull;
        constexpr static __uint128_t pow10_20 = pow10_10 * pow10_10;

        __uint128_t y;
        if (x >= pow10_20) { // 10^20
            div_mod<__uint128_t>(y, x, pow10_20);
            put_u64(uint64_t(y));
            div_mod<__uint128_t>(y, x, __uint128_t(10000000000000000ull));
            put_cstr(leading_zero[y]);
            div_mod<__uint128_t>(y, x, __uint128_t(1000000000000ull));
            put_cstr(leading_zero[y]);
            div_mod<__uint128_t>(y, x, __uint128_t(100000000ull));
            put_cstr(leading_zero[y]);
            div_mod<__uint128_t>(y, x, __uint128_t(10000ull));
            put_cstr(leading_zero[y]);
            put_cstr(leading_zero[x]);
        } else if (x >= __uint128_t(10000)) { // 10^4
            div_mod<__uint128_t>(y, x, __uint128_t(10000));
            put_u64(uint64_t(y));
            put_cstr(leading_zero[x]);
        } else put_cstr(helper[x]);
    }

    void put_i128(__int128_t x) {
        if (x < 0) {
            put_char('-');
            put_u128(-x);
        } else put_u128(x);
    }

    template <class T, is_unsigned_t<T> * = nullptr> Printer &operator<<(T x) {
        if constexpr (sizeof(T) <= 4) put_u32(x);
        else if constexpr (sizeof(T) <= 8) put_u64(x);
        else put_u128(x);
        return *this;
    }

    template <class T, is_signed_t<T> * = nullptr> Printer &operator<<(T x) {
        if constexpr (sizeof(T) <= 4) put_i32(x);
        else if constexpr (sizeof(T) <= 8) put_i64(x);
        else put_i128(x);
        return *this;
    }

    Printer &operator<<(char x) {
        put_char(x);
        return *this;
    }

    Printer &operator<<(const std::string &x) {
        for (char c : x) put_char(c);
        return *this;
    }

    Printer &operator<<(const char *x) {
        put_cstr(x);
        return *this;
    }

    // std::cout << std::endl; は関数ポインタを渡しているらしい
    Printer &operator<<(endl_struct_t) {
        put_char('\n');
        flush();
        return *this;
    }
};

char Scanner::buf[Scanner::INPUT_BUF];
char Printer::buf[Printer::OUTPUT_BUF];
char Printer::helper[10000][5];
char Printer::leading_zero[10000][5];

} // namespace fastio

#if defined(INTERACTIVE) || defined(USE_STDIO)
auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;
#else
fastio::Scanner kin;
fastio::Printer kout;
fastio::endl_struct_t kendl;
#endif

} // namespace kk2

#endif // TEMPLATE_FASTIO_HPP

// #include "fastio.hpp"
#ifndef TEMPLATE_TYPE_ALIAS_HPP
#define TEMPLATE_TYPE_ALIAS_HPP 1

#include <utility>
#include <vector>
#include <queue>
#include <functional>

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;

template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;

template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#endif // TEMPLATE_TYPE_ALIAS_HPP

// #include "type_alias.hpp"
#ifndef TEMPLATE_CONSTANT_HPP
#define TEMPLATE_CONSTANT_HPP 1

template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;

constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;

#endif // TEMPLATE_CONSTANT_HPP

// #include "constant.hpp"
#ifndef TEMPLATE_FUNCTIONAL_UTIL_HPP
#define TEMPLATE_FUNCTIONAL_UTIL_HPP 1

#include <algorithm>
#include <vector>

namespace kk2 {

template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
    if constexpr (sizeof...(sizes) == 0) {
        return std::vector<T>(first);
    } else {
        return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));
    }
}

template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
    std::fill(std::begin(v), std::end(v), T(x));
}

template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {
    for (auto &u : v) fill_all(u, x);
}

} // namespace kk2

template <class T, class S> inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template <class T, class S> inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

#endif // TEMPLATE_FUNCTIONAL_UTIL_HPP

// #include "function_util.hpp"
#ifndef TEMPLATE_MACROS_HPP
#define TEMPLATE_MACROS_HPP 1

#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)

#define fi first
#define se second
#define all(p) p.begin(), p.end()

#endif // TEMPLATE_MACROS_HPP

// #include "macros.hpp"
#ifndef TEMPLATE_IO_UTIL_HPP
#define TEMPLATE_IO_UTIL_HPP 1

#include <array>
#include <utility>
#include <vector>

// #include "../type_traits/type_traits.hpp"

// なんかoj verifyはプロトタイプ宣言が落ちる

namespace impl {

struct read {
    template <class IStream, class T>
    static void all_read(IStream &is, T &x) {
        is >> x;
    }

    template <class IStream, class T, class U>
    static void all_read(IStream &is, std::pair<T, U> &p) {
        all_read(is, p.first);
        all_read(is, p.second);
    }

    template <class IStream, class T>
    static void all_read(IStream &is, std::vector<T> &v) {
        for (T &x : v) all_read(is, x);
    }

    template <class IStream, class T, size_t F>
    static void all_read(IStream &is, std::array<T, F> &a) {
        for (T &x : a) all_read(is, x);
    }
};

struct write {
    template <class OStream, class T>
    static void all_write(OStream &os, const T &x) {
        os << x;
    }

    template <class OStream, class T, class U>
    static void all_write(OStream &os, const std::pair<T, U> &p) {
        all_write(os, p.first);
        all_write(os, ' ');
        all_write(os, p.second);
    }

    template <class OStream, class T>
    static void all_write(OStream &os, const std::vector<T> &v) {
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) all_write(os, ' ');
            all_write(os, v[i]);
        }
    }

    template <class OStream, class T, size_t F>
    static void all_write(OStream &os, const std::array<T, F> &a) {
        for (int i = 0; i < (int)F; ++i) {
            if (i) all_write(os, ' ');
            all_write(os, a[i]);
        }
    }
};

} // namespace impl

template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
    impl::read::all_read(is, p);
    return is;
}

template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
    impl::read::all_read(is, v);
    return is;
}

template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
    impl::read::all_read(is, a);
    return is;
}

template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
    impl::write::all_write(os, p);
    return os;
}

template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
    impl::write::all_write(os, v);
    return os;
}

template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
    impl::write::all_write(os, a);
    return os;
}

#endif // TEMPLATE_IO_UTIL_HPP

// #include "io_util.hpp"

using kk2::kendl;
using kk2::kin;
using kk2::kout;

void Yes(bool b = 1) {
    kout << (b ? "Yes\n" : "No\n");
}

void No(bool b = 1) {
    kout << (b ? "No\n" : "Yes\n");
}

void YES(bool b = 1) {
    kout << (b ? "YES\n" : "NO\n");
}

void NO(bool b = 1) {
    kout << (b ? "NO\n" : "YES\n");
}

void yes(bool b = 1) {
    kout << (b ? "yes\n" : "no\n");
}

void no(bool b = 1) {
    kout << (b ? "no\n" : "yes\n");
}

#endif // TEMPLATE

// #include "../../template/template.hpp"
using namespace std;

int main() {
    int n, m;
    kin >> n >> m;
    kk2::AdjList g(n, m);
    g.input(kin, 1);

    kk2::BlockCutTree bct(g);
    kk2::HeavyLightDecomposition hld(bct.forest);

    int q;
    kin >> q;

    rep (q) {
        int x, y;
        kin >> x >> y;
        --x, --y;
        if (bct.comp_v[x] == bct.comp_v[y]) {
            kout << 0 << "\n";
            continue;
        }
        int res = hld.dist(bct.comp_v[x], bct.comp_v[y]);
        if (bct.is_articulation(x)) --res;
        if (bct.is_articulation(y)) --res;
        kout << res / 2 << "\n";
    }

    return 0;
}

// converted!!
// Author: kk2
// 2025-01-01 03:46:01