結果
| 問題 | No.1600 Many Shortest Path Problems |
| ユーザー |
👑  hitonanode
|
| 提出日時 | 2021-07-13 00:21:33 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 21,540 bytes |
| コンパイル時間 | 2,947 ms |
| コンパイル使用メモリ | 183,504 KB |
| 実行使用メモリ | 130,288 KB |
| 最終ジャッジ日時 | 2023-09-14 20:47:44 |
| 合計ジャッジ時間 | 26,468 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 2 ms
4,376 KB |
| testcase_04 | AC | 725 ms
126,300 KB |
| testcase_05 | AC | 705 ms
126,048 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,380 KB |
| testcase_08 | AC | 2 ms
4,376 KB |
| testcase_09 | AC | 2 ms
4,376 KB |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 1 ms
4,380 KB |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 1 ms
4,376 KB |
| testcase_20 | AC | 1 ms
4,376 KB |
| testcase_21 | WA | - |
| testcase_22 | AC | 2 ms
4,380 KB |
| testcase_23 | AC | 1 ms
4,380 KB |
| testcase_24 | WA | - |
| testcase_25 | AC | 2 ms
4,376 KB |
| testcase_26 | AC | 2 ms
4,376 KB |
| testcase_27 | AC | 2 ms
4,376 KB |
| testcase_28 | AC | 1 ms
4,376 KB |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | AC | 2 ms
4,380 KB |
| testcase_34 | AC | 1 ms
4,376 KB |
| testcase_35 | AC | 429 ms
126,612 KB |
| testcase_36 | AC | 464 ms
127,408 KB |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | AC | 2 ms
4,380 KB |
| testcase_40 | AC | 851 ms
74,832 KB |
| testcase_41 | AC | 521 ms
75,776 KB |
| testcase_42 | WA | - |
| testcase_43 | AC | 451 ms
74,612 KB |
| testcase_44 | AC | 414 ms
73,652 KB |
| testcase_45 | WA | - |
| testcase_46 | AC | 569 ms
73,060 KB |
| testcase_47 | AC | 690 ms
74,980 KB |
| testcase_48 | AC | 604 ms
73,408 KB |
| testcase_49 | AC | 2 ms
4,376 KB |
| testcase_50 | AC | 1 ms
4,380 KB |
| testcase_51 | AC | 2 ms
4,380 KB |
| testcase_52 | AC | 1 ms
4,380 KB |
| testcase_53 | AC | 2 ms
4,376 KB |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template <typename T> vector<T> sort_unique(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <typename T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <typename T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T, size_t sz> ostream &operator<<(ostream &os, const array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
#if __cplusplus >= 201703L
template <typename... T> istream &operator>>(istream &is, tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <typename... T> ostream &operator<<(ostream &os, const tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
#endif
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T, typename TH> ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <typename TK, typename TV, typename TH> ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl
#define dbgif(cond, x) ((cond) ? cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl : cerr)
#else
#define dbg(x) (x)
#define dbgif(cond, x) 0
#endif
template <int md> struct ModInt {
#if __cplusplus >= 201402L
#define MDCONST constexpr
#else
#define MDCONST
#endif
using lint = long long;
MDCONST static int mod() { return md; }
static int get_primitive_root() {
static int primitive_root = 0;
if (!primitive_root) {
primitive_root = [&]() {
std::set<int> fac;
int v = md - 1;
for (lint i = 2; i * i <= v; i++)
while (v % i == 0) fac.insert(i), v /= i;
if (v > 1) fac.insert(v);
for (int g = 1; g < md; g++) {
bool ok = true;
for (auto i : fac)
if (ModInt(g).pow((md - 1) / i) == 1) {
ok = false;
break;
}
if (ok) return g;
}
return -1;
}();
}
return primitive_root;
}
int val;
MDCONST ModInt() : val(0) {}
MDCONST ModInt &_setval(lint v) { return val = (v >= md ? v - md : v), *this; }
MDCONST ModInt(lint v) { _setval(v % md + md); }
MDCONST explicit operator bool() const { return val != 0; }
MDCONST ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val + x.val); }
MDCONST ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val - x.val + md); }
MDCONST ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val * x.val % md); }
MDCONST ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val * x.inv() % md); }
MDCONST ModInt operator-() const { return ModInt()._setval(md - val); }
MDCONST ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
MDCONST ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
MDCONST ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
MDCONST ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
friend MDCONST ModInt operator+(lint a, const ModInt &x) { return ModInt()._setval(a % md + x.val); }
friend MDCONST ModInt operator-(lint a, const ModInt &x) { return ModInt()._setval(a % md - x.val + md); }
friend MDCONST ModInt operator*(lint a, const ModInt &x) { return ModInt()._setval(a % md * x.val % md); }
friend MDCONST ModInt operator/(lint a, const ModInt &x) {
return ModInt()._setval(a % md * x.inv() % md);
}
MDCONST bool operator==(const ModInt &x) const { return val == x.val; }
MDCONST bool operator!=(const ModInt &x) const { return val != x.val; }
MDCONST bool operator<(const ModInt &x) const { return val < x.val; } // To use std::map<ModInt, T>
friend std::istream &operator>>(std::istream &is, ModInt &x) {
lint t;
return is >> t, x = ModInt(t), is;
}
MDCONST friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val; }
MDCONST ModInt pow(lint n) const {
ModInt ans = 1, tmp = *this;
while (n) {
if (n & 1) ans *= tmp;
tmp *= tmp, n >>= 1;
}
return ans;
}
static std::vector<ModInt> facs, facinvs, invs;
MDCONST static void _precalculation(int N) {
int l0 = facs.size();
if (N > md) N = md;
if (N <= l0) return;
facs.resize(N), facinvs.resize(N), invs.resize(N);
for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i;
facinvs[N - 1] = facs.back().pow(md - 2);
for (int i = N - 2; i >= l0; i--) facinvs[i] = facinvs[i + 1] * (i + 1);
for (int i = N - 1; i >= l0; i--) invs[i] = facinvs[i] * facs[i - 1];
}
MDCONST lint inv() const {
if (this->val < std::min(md >> 1, 1 << 21)) {
while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
return invs[this->val].val;
} else {
return this->pow(md - 2).val;
}
}
MDCONST ModInt fac() const {
while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
return facs[this->val];
}
MDCONST ModInt facinv() const {
while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
return facinvs[this->val];
}
MDCONST ModInt doublefac() const {
lint k = (this->val + 1) / 2;
return (this->val & 1) ? ModInt(k * 2).fac() / (ModInt(2).pow(k) * ModInt(k).fac())
: ModInt(k).fac() * ModInt(2).pow(k);
}
MDCONST ModInt nCr(const ModInt &r) const {
return (this->val < r.val) ? 0 : this->fac() * (*this - r).facinv() * r.facinv();
}
MDCONST ModInt nPr(const ModInt &r) const {
return (this->val < r.val) ? 0 : this->fac() * (*this - r).facinv();
}
ModInt sqrt() const {
if (val == 0) return 0;
if (md == 2) return val;
if (pow((md - 1) / 2) != 1) return 0;
ModInt b = 1;
while (b.pow((md - 1) / 2) == 1) b += 1;
int e = 0, m = md - 1;
while (m % 2 == 0) m >>= 1, e++;
ModInt x = pow((m - 1) / 2), y = (*this) * x * x;
x *= (*this);
ModInt z = b.pow(m);
while (y != 1) {
int j = 0;
ModInt t = y;
while (t != 1) j++, t *= t;
z = z.pow(1LL << (e - j - 1));
x *= z, z *= z, y *= z;
e = j;
}
return ModInt(std::min(x.val, md - x.val));
}
};
template <int md> std::vector<ModInt<md>> ModInt<md>::facs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::facinvs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::invs = {0};
using mint = ModInt<1000000007>;
// UnionFind Tree (0-indexed), based on size of each disjoint set
struct UnionFind {
std::vector<int> par, cou;
UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }
int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (cou[x] < cou[y]) std::swap(x, y);
par[y] = x, cou[x] += cou[y];
return true;
}
int count(int x) { return cou[find(x)]; }
bool same(int x, int y) { return find(x) == find(y); }
};
// Incremental Bridge-Connectivity
// two-edge-connected components
// Reference: <https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity>
// <https://ei1333.github.io/library/graph/connected-components/incremental-bridge-connectivity.cpp>
struct IncrementalBridgeConnectivity {
int V;
int nb_bridge;
UnionFind con, bicon;
std::vector<int> bbf;
int _bicon_par(int x) { return bbf[x] == -1 ? -1 : bicon.find(bbf[x]); }
int _lca(int x, int y) {
std::unordered_set<int> us;
while (true) {
if (x != -1) {
if (!us.insert(x).second) { return x; }
x = _bicon_par(x);
}
std::swap(x, y);
}
}
void _compress(int now, int lca) {
while (bicon.find(now) != bicon.find(lca)) {
int nxt = _bicon_par(now);
bbf[now] = bbf[lca], bicon.unite(now, lca), now = nxt, nb_bridge--;
}
}
IncrementalBridgeConnectivity(int v = 0) : V(v), nb_bridge(0), con(v), bicon(v), bbf(v, -1) {}
void add_edge(int u, int v) {
assert(u >= 0 and u < V);
assert(v >= 0 and v < V);
u = bicon.find(u), v = bicon.find(v);
if (con.find(u) == con.find(v)) {
int lca = _lca(u, v);
_compress(u, lca), _compress(v, lca);
} else {
if (con.count(u) > con.count(v)) std::swap(u, v);
for (int now = u, pre = v; now != -1;) {
int nxt = _bicon_par(now);
bbf[now] = pre, pre = now, now = nxt;
}
con.unite(u, v), nb_bridge++;
}
}
int count_bridge() const { return nb_bridge; }
bool two_edge_connected(int x, int y) { return bicon.same(x, y); }
int find(int x) { return bicon.find(x); }
};
// lowest common ancestor (LCA) class for undirected weighted tree
// 無向重み付きグラフの最小共通祖先
// <https://yukicoder.me/submissions/392383>
struct UndirectedWeightedTree {
using T = long long; // Arbitrary data structure (operator+, operator- must be defined)
int INVALID = -1;
int V, lgV;
int E;
int root;
std::vector<std::vector<std::pair<int, int>>> adj; // (nxt_vertex, edge_id)
// vector<pint> edge; // edges[edge_id] = (vertex_id, vertex_id)
std::vector<T> weight; // w[edge_id]
std::vector<int> par; // parent_vertex_id[vertex_id]
std::vector<int> depth; // depth_from_root[vertex_id]
std::vector<T> acc_weight; // w_sum_from_root[vertex_id]
void _fix_root_dfs(int now, int prv, int prv_edge_id) {
par[now] = prv;
if (prv_edge_id != INVALID) acc_weight[now] = acc_weight[prv] + weight[prv_edge_id];
for (auto nxt : adj[now])
if (nxt.first != prv) {
depth[nxt.first] = depth[now] + 1;
_fix_root_dfs(nxt.first, now, nxt.second);
}
}
UndirectedWeightedTree() = default;
UndirectedWeightedTree(int N) : V(N), E(0), adj(N) {
lgV = 1;
while (1 << lgV < V) lgV++;
}
void add_edge(int u, int v, T w) {
adj[u].emplace_back(v, E);
adj[v].emplace_back(u, E);
// edge.emplace_back(u, v);
weight.emplace_back(w);
E++;
}
void fix_root(int r) {
root = r;
par.resize(V);
depth.resize(V);
depth[r] = 0;
acc_weight.resize(V);
acc_weight[r] = 0;
_fix_root_dfs(root, INVALID, INVALID);
}
std::vector<std::vector<int>> doubling;
void doubling_precalc() {
doubling.assign(lgV, std::vector<int>(V));
doubling[0] = par;
for (int d = 0; d < lgV - 1; d++)
for (int i = 0; i < V; i++) {
if (doubling[d][i] == INVALID)
doubling[d + 1][i] = INVALID;
else
doubling[d + 1][i] = doubling[d][doubling[d][i]];
}
}
int kth_parent(int x, int k) {
if (depth[x] < k) return INVALID;
for (int d = 0; d < lgV; d++) {
if (x == INVALID) return INVALID;
if (k & (1 << d)) x = doubling[d][x];
}
return x;
}
int lowest_common_ancestor(int u, int v) {
if (depth[u] > depth[v]) std::swap(u, v);
v = kth_parent(v, depth[v] - depth[u]);
if (u == v) return u;
for (int d = lgV - 1; d >= 0; d--) {
if (doubling[d][u] != doubling[d][v]) u = doubling[d][u], v = doubling[d][v];
}
return par[u];
}
T path_length(int u, int v) {
// Not distance, but the sum of weights
int r = lowest_common_ancestor(u, v);
return (acc_weight[u] - acc_weight[r]) + (acc_weight[v] - acc_weight[r]);
}
};
// Range Minimum Query for static sequence by sparse table
// Complexity: (N \log N)$ for precalculation, (1)$ per query
template <typename T> struct StaticRMQ {
inline T func(const T &l, const T &r) const noexcept { return std::min<T>(l, r); }
int N, lgN;
T defaultT;
std::vector<std::vector<T>> data;
std::vector<int> lgx_table;
StaticRMQ() = default;
StaticRMQ(const std::vector<T> &sequence, T defaultT) : N(sequence.size()), defaultT(defaultT) {
lgx_table.resize(N + 1);
for (int i = 2; i < N + 1; i++) lgx_table[i] = lgx_table[i >> 1] + 1;
lgN = lgx_table[N] + 1;
data.assign(lgN, std::vector<T>(N, defaultT));
data[0] = sequence;
for (int d = 1; d < lgN; d++) {
for (int i = 0; i + (1 << d) <= N; i++) {
data[d][i] = func(data[d - 1][i], data[d - 1][i + (1 << (d - 1))]);
}
}
}
T get(int l, int r) const { // [l, r), 0-indexed
assert(l >= 0 and r <= N);
if (l >= r) return defaultT;
int d = lgx_table[r - l];
return func(data[d][l], data[d][r - (1 << d)]);
}
};
struct TreeLCA {
const int N;
std::vector<std::vector<int>> to;
bool built;
TreeLCA(int V = 0) : N(V), to(V), built(false) {}
void add_edge(int u, int v) {
assert(0 <= u and u < N);
assert(0 <= v and v < N);
assert(u != v);
to[u].push_back(v);
to[v].push_back(u);
}
using P = std::pair<int, int>;
std::vector<int> subtree_begin;
std::vector<P> vis_order;
std::vector<int> depth;
void _build_dfs(int now, int prv, int dnow) {
subtree_begin[now] = vis_order.size();
vis_order.emplace_back(dnow, now);
depth[now] = dnow;
for (auto &&nxt : to[now]) {
if (nxt != prv) {
_build_dfs(nxt, now, dnow + 1);
vis_order.emplace_back(dnow, now);
}
}
}
StaticRMQ<P> rmq;
void build(int root = 0) {
assert(root >= 0 and root < N);
built = true;
subtree_begin.resize(N);
vis_order.reserve(N * 2);
depth.resize(N);
_build_dfs(root, -1, 0);
rmq = {vis_order, P{N, -1}};
}
int lca(int u, int v) {
assert(0 <= u and u < N);
assert(0 <= v and v < N);
if (!built) build();
auto a = subtree_begin[u], b = subtree_begin[v];
if (a > b) std::swap(a, b);
return rmq.get(a, b + 1).second;
};
int lca3(int a, int b, int c) {
return lca(a, b) ^ lca(b, c) ^ lca(c, a);
}
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
};
int main() {
int N, M;
cin >> N >> M;
UndirectedWeightedTree tree(N);
TreeLCA tree1(N);
vector<pint> edges, tree_edges;
vector<mint> pow2{1};
UnionFind uf(N);
vector<int> additional_eids;
REP(e, M) {
int a, b;
cin >> a >> b;
a--, b--;
edges.emplace_back(a, b);
auto p = pow2.back() * 2;
pow2.push_back(p);
if (uf.unite(a, b)) {
tree.add_edge(a, b, p.val);
tree1.add_edge(a, b);
tree_edges.emplace_back(a, b);
} else {
additional_eids.push_back(e);
}
}
tree.fix_root(0);
tree1.build();
tree.doubling_precalc();
int Q;
cin >> Q;
vector<int> x(Q), y(Q), z(Q), u(Q), v(Q);
vector<int> ret(Q, -1);
vector<int> lo(Q, -1), hi(Q, additional_eids.size() + 1);
REP(q, Q) {
cin >> x[q] >> y[q] >> z[q];
x[q]--, y[q]--, z[q]--;
bool edge_on_line = false;
if (!binary_search(additional_eids.begin(), additional_eids.end(), z[q])) {
tie(u[q], v[q]) = edges[z[q]];
if (tree1.lca3(x[q], y[q], u[q]) == u[q] and tree1.lca3(x[q], y[q], v[q]) == v[q]) {
edge_on_line = true;
}
}
if (!edge_on_line) {
lo[q] = -1, hi[q] = 0;
ret[q] = mint(tree.path_length(x[q], y[q])).val;
} else {
lo[q] = 0;
}
}
dbg("OK");
IncrementalBridgeConnectivity conn_(N);
for (auto [a, b] : tree_edges) conn_.add_edge(a, b);
while (true) {
vector<pint> t2q;
REP(q, Q) {
if (lo[q] + 1 < hi[q]) {
int n = (lo[q] + hi[q]) / 2;
t2q.emplace_back(n, q);
}
}
if (t2q.empty()) break;
sort(t2q.begin(), t2q.end());
int added = 0;
auto conn = conn_;
for (auto [t, q] : t2q) {
while (added < t) {
auto [u, v] = edges[additional_eids[added++]];
conn.add_edge(u, v);
}
(conn.two_edge_connected(u[q], v[q]) ? hi[q] : lo[q]) = t;
}
}
REP(q, Q) if (ret[q] < 0) {
if (lo[q] < int(additional_eids.size())) {
int e = additional_eids[lo[q]];
auto [u, v] = edges[e];
if (tree1.distance(x[q], u) > tree1.distance(x[q], v)) swap(u, v);
ret[q] = mint(tree.path_length(x[q], u) + tree.path_length(y[q], v) + pow2[e + 1]).val;
}
}
for (auto x : ret) cout << x << '\n';
}