Shortest non-separating st-path on chordal graphs

SNSCG.cpp

#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <limits>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

inline size_t next_power_of_2(size_t n) {
    if (n <= 1)
        return 1;
    return 1ull << (64 - __builtin_clzll(n - 1));
}

using namespace std;

constexpr int64_t INF = numeric_limits<int64_t>::max() / 2;
constexpr int32_t INF_INT = numeric_limits<int32_t>::max();

typedef int32_t Vertex;
typedef vector<Vertex> Path;

using BoolVector = vector<bool>;

constexpr Vertex V_NONE = 0;

typedef uint64_t PackedKey;

struct optimized_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    template <typename T> size_t operator()(T x) const {

        static const uint64_t FIXED_RANDOM =
            reinterpret_cast<uint64_t>(&FIXED_RANDOM);

        return splitmix64(static_cast<uint64_t>(x) + FIXED_RANDOM);
    }
};

inline PackedKey edge_key(Vertex u, Vertex v) {
    if (u > v)
        swap(u, v);
    return ((uint64_t)v << 32) | (uint32_t)u;
}

inline PackedKey directed_edge_key(Vertex u, Vertex v) {
    return ((uint64_t)u << 32) | (uint32_t)v;
}

inline PackedKey lr_key(int32_t r_id, Vertex u) {
    return ((uint64_t)r_id << 32) | (uint32_t)u;
}

inline pair<Vertex, Vertex> unpack_edge_key(PackedKey key) {
    return {(Vertex)(key & 0xFFFFFFFF), (Vertex)(key >> 32)};
}

template <typename V>
using OptimizedMap = unordered_map<PackedKey, V, optimized_hash>;

template <typename K> using OptimizedSet = unordered_set<K, optimized_hash>;

struct FlatMap {
    struct Slot {
        PackedKey k;
        Vertex v;
    };
    vector<Slot> tab;
    vector<uint8_t> used;
    size_t mask;

    FlatMap() : mask(0) {}

    void init(size_t capacity_estimate) {
        if (capacity_estimate == 0) {
            mask = 0;
            return;
        }

        size_t cap_pow2 =
            next_power_of_2(capacity_estimate + capacity_estimate / 2);
        if (cap_pow2 < 16)
            cap_pow2 = 16;

        if (cap_pow2 == 0) {
            mask = 0;
            return;
        }

        tab.assign(cap_pow2, {});
        used.assign(cap_pow2, 0);
        mask = cap_pow2 - 1;
    }

    inline void emplace(PackedKey k, Vertex v) {
        if (mask == 0)
            return;
        size_t i = optimized_hash::splitmix64(k) & mask;
        while (used[i] && tab[i].k != k)
            i = (i + 1) & mask;

        if (!used[i]) {
            used[i] = 1;
            tab[i].k = k;
            tab[i].v = v;
        }
    }

    inline Vertex get(PackedKey k) const {
        if (mask == 0)
            return V_NONE;
        size_t i = optimized_hash::splitmix64(k) & mask;
        while (used[i]) {
            if (tab[i].k == k)
                return tab[i].v;
            i = (i + 1) & mask;
        }
        return V_NONE;
    }
};

struct Edge {
    int64_t weight;
    Vertex to;
    int32_t id;
};

struct OriginalEdge {
    Vertex u, v;
    int64_t weight;
    int32_t id;
    OriginalEdge(Vertex u, Vertex v, int64_t w, int32_t id)
        : u(u), v(v), weight(w), id(id) {}
};

class Graph {
  public:
    vector<vector<Edge>> adj;
    int32_t N;
    bool finalized = false;

    vector<OriginalEdge> edge_storage;
    vector<const OriginalEdge*> edge_list;
    vector<const OriginalEdge*> edge_id_to_ptr;

    int32_t max_edge_id = -1;

    Graph() : N(0) {}

    Graph(int32_t vertex_count, int32_t edge_count) {
        N = vertex_count + 1;
        adj.resize(N);

        if (edge_count > 0) {
            edge_storage.reserve(edge_count);
            edge_list.reserve(edge_count);

            edge_id_to_ptr.reserve(edge_count);
        }
    }

    void finalize_construction() {
        if (finalized)
            return;

        for (Vertex u = 1; u < N; ++u) {
            sort(adj[u].begin(), adj[u].end(),
                 [](const Edge& a, const Edge& b) { return a.to < b.to; });
        }
        finalized = true;
    }

    void ensure_vertex_capacity(Vertex u) {
        if (u >= N) {
            N = u + 1;
            adj.resize(N);
            finalized = false;
        }
    }

    void ensure_id_capacity(int32_t id) {
        if (id != -1 && id >= static_cast<int32_t>(edge_id_to_ptr.size())) {
            edge_id_to_ptr.resize(id + 1, nullptr);
        }
    }

    void add_directed_edge(Vertex u, Vertex v, int64_t w, int32_t id) {
        adj[u].push_back({w, v, id});
    }

    void add_edge(Vertex u, Vertex v, int64_t w, int32_t id,
                  const OriginalEdge* existing_ptr = nullptr) {

        if (id != -1) {
            if (id > max_edge_id) {
                max_edge_id = id;
                ensure_id_capacity(id);
            } else if (id >= static_cast<int32_t>(edge_id_to_ptr.size())) {
                ensure_id_capacity(id);
            }

            if (id < static_cast<int32_t>(edge_id_to_ptr.size()) &&
                edge_id_to_ptr[id]) {
                return;
            }
        }

        if (max(u, v) >= N) {
            ensure_vertex_capacity(max(u, v));
        }

        add_directed_edge(u, v, w, id);
        add_directed_edge(v, u, w, id);
        finalized = false;

        if (id != -1) {
            const OriginalEdge* ptr;
            if (existing_ptr) {
                ptr = existing_ptr;
            } else {

                edge_storage.emplace_back(u, v, w, id);
                ptr = &edge_storage.back();
            }
            edge_list.push_back(ptr);

            if (id < static_cast<int32_t>(edge_id_to_ptr.size())) {
                edge_id_to_ptr[id] = ptr;
            }
        }
    }

    inline pair<int64_t, int32_t> get_edge_info(Vertex u, Vertex v) const {
        if (u >= N || v >= N || u == 0 || v == 0)
            return {INF, -1};

        const vector<Edge>* adj_list;
        Vertex target;

        if (adj[u].size() <= adj[v].size()) {
            adj_list = &adj[u];
            target = v;
        } else {
            adj_list = &adj[v];
            target = u;
        }

        if (finalized) {

            auto it = std::lower_bound(
                adj_list->begin(), adj_list->end(), target,
                [](const Edge& e, Vertex t) { return e.to < t; });
            if (it != adj_list->end() && it->to == target) {
                return {it->weight, it->id};
            }
        } else {

            for (const auto& edge : *adj_list) {
                if (edge.to == target) {
                    return {edge.weight, edge.id};
                }
            }
        }
        return {INF, -1};
    }

    bool are_adjacent(Vertex u, Vertex v) const {
        return get_edge_info(u, v).second != -1;
    }

    const OriginalEdge* get_edge_ptr(int32_t id) const {
        if (id < 0 || id >= static_cast<int32_t>(edge_id_to_ptr.size()))
            return nullptr;
        return edge_id_to_ptr[id];
    }
};

class MultiGraph {
  public:
    vector<vector<pair<Vertex, int32_t>>> adj;
    int32_t N;

    MultiGraph(int32_t size) : N(size) { adj.resize(N); }
};

inline int64_t get_edge_length(const Graph& G, Vertex u, Vertex v) {
    return G.get_edge_info(u, v).first;
}

inline int32_t get_edge_id(const Graph& G, Vertex u, Vertex v) {
    return G.get_edge_info(u, v).second;
}

inline vector<int32_t> get_P_indices_vec(const Path& P, int32_t N) {
    vector<int32_t> indices(N, -1);
    for (int32_t i = 0; i < static_cast<int32_t>(P.size()); ++i) {
        if (P[i] > 0 && P[i] < N) {
            indices[P[i]] = i;
        }
    }
    return indices;
}

inline bool is_useful_weighted(const Path& r, const vector<int64_t>& weights,
                               const Graph& G) {
    if (r.size() < 3)
        return false;

    for (int32_t i = 0; i <= static_cast<int32_t>(r.size()) - 3; ++i) {
        int64_t len_path = weights[i] + weights[i + 1];

        int64_t len_edge = get_edge_length(G, r[i], r[i + 2]);

        if (len_edge != INF && len_path >= len_edge) {
            return false;
        }
    }
    return true;
}

inline pair<int64_t, Path> dijkstra(const Graph& G, Vertex S, Vertex T,
                                    const BoolVector& is_forbidden_v = {},
                                    const BoolVector& is_forbidden_e = {}) {

    if (S <= 0 || S >= G.N || T <= 0 || T >= G.N)
        return {INF, {}};

    if (!is_forbidden_v.empty()) {
        if ((S < static_cast<int32_t>(is_forbidden_v.size()) &&
             is_forbidden_v[S]) ||
            (T < static_cast<int32_t>(is_forbidden_v.size()) &&
             is_forbidden_v[T]))
            return {INF, {}};
    }

    vector<int64_t> dist(G.N, INF);
    vector<Vertex> parent(G.N, V_NONE);

    using PQElement = pair<int64_t, Vertex>;
    priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pq;

    dist[S] = 0;
    pq.emplace(0, S);

    while (!pq.empty()) {
        int64_t d = pq.top().first;
        Vertex u = pq.top().second;
        pq.pop();

        if (d > dist[u])
            continue;
        if (u == T)
            break;

        for (const auto& edge : G.adj[u]) {
            Vertex v = edge.to;

            if (!is_forbidden_v.empty() &&
                v < static_cast<int32_t>(is_forbidden_v.size()) &&
                is_forbidden_v[v])
                continue;

            if (edge.id != -1 && !is_forbidden_e.empty() &&
                edge.id < static_cast<int32_t>(is_forbidden_e.size()) &&
                is_forbidden_e[edge.id])
                continue;

            int64_t new_dist = dist[u] + edge.weight;

            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                parent[v] = u;
                pq.emplace(dist[v], v);
            }
        }
    }

    if (dist[T] == INF) {
        return {INF, {}};
    }

    Path path;
    Vertex curr = T;
    while (curr != S) {
        path.push_back(curr);
        if (parent[curr] == V_NONE)
            return {INF, {}};
        curr = parent[curr];
    }
    path.push_back(S);
    reverse(path.begin(), path.end());
    return {dist[T], path};
}

class BridgeFinder {
  public:
    const Graph& G;
    vector<int32_t> tin, low;
    int timer;

    BoolVector is_bridge;
    int max_id = -1;

    BridgeFinder(const Graph& G) : G(G) {}

    struct DFSState {
        Vertex v;
        Vertex p;
        int edge_id_in;
        size_t neighbor_index;
    };

    inline void find_Bridges() {
        timer = 0;
        tin.assign(G.N, -1);
        low.assign(G.N, -1);

        vector<int32_t> bridge_ids_vec;
        bridge_ids_vec.reserve(G.edge_list.size());
        vector<DFSState> stack;
        if (G.N > 1)
            stack.reserve(G.N);

        for (Vertex start_node = 1; start_node < G.N; ++start_node) {
            if (tin[start_node] != -1)
                continue;

            stack.push_back({start_node, V_NONE, -1, 0});

            while (!stack.empty()) {
                DFSState& state = stack.back();

                if (state.neighbor_index == 0) {
                    if (tin[state.v] == -1) {
                        tin[state.v] = low[state.v] = timer++;
                    }
                }

                const auto& adj_v = G.adj[state.v];
                bool pushed_child = false;

                while (state.neighbor_index < adj_v.size()) {
                    const auto& edge = adj_v[state.neighbor_index];
                    Vertex to = edge.to;
                    state.neighbor_index++;

                    if (to == state.p)
                        continue;

                    if (tin[to] != -1) {
                        low[state.v] = min(low[state.v], tin[to]);
                    } else {
                        stack.push_back({to, state.v, edge.id, 0});
                        pushed_child = true;
                        break;
                    }
                }

                if (pushed_child) {
                    continue;
                }

                Vertex v = state.v;
                Vertex p = state.p;
                int32_t edge_id_in = state.edge_id_in;
                stack.pop_back();

                if (p != V_NONE) {
                    low[p] = min(low[p], low[v]);

                    if (low[v] > tin[p]) {
                        if (edge_id_in != -1) {
                            bridge_ids_vec.push_back(edge_id_in);
                            if (edge_id_in > max_id) {
                                max_id = edge_id_in;
                            }
                        }
                    }
                }
            }
        }

        if (max_id != -1) {
            is_bridge.assign(max_id + 1, false);
            for (int32_t id : bridge_ids_vec) {
                is_bridge[id] = true;
            }
        }
    }
};

class BCCFinder {
  public:
    const Graph& G;

    const BoolVector* forbidden_edge_ids = nullptr;

    vector<int32_t> tin, low;
    int32_t timer;

    vector<vector<Vertex>> BCCs;

    vector<int> mark_v_internal;
    int stamp_counter_internal;

    vector<vector<int32_t>> vertex_BCC_membership;

    BoolVector is_ap;
    vector<int32_t> edge_stack;
    vector<int32_t> edge_to_BCC;

    BCCFinder(const Graph& G, const BoolVector* forbidden = nullptr)
        : G(G), forbidden_edge_ids(forbidden) {}

    struct DFSState {
        Vertex v;
        Vertex p;
        int32_t edge_id_in;
        size_t neighbor_index;
        int32_t children_count;
    };

    inline void find_BCCs() {

        timer = 0;
        tin.assign(G.N, -1);
        low.assign(G.N, -1);
        BCCs.clear();

        stamp_counter_internal = 1;
        mark_v_internal.assign(G.N, 0);

        vertex_BCC_membership.assign(G.N, {});

        is_ap.assign(G.N, false);
        edge_stack.clear();
        edge_stack.reserve(G.edge_list.size());

        if (G.max_edge_id != -1) {
            edge_to_BCC.assign(G.max_edge_id + 1, -1);
        } else {
            edge_to_BCC.clear();
        }

        vector<DFSState> stack;
        if (G.N > 1)
            stack.reserve(G.N);

        for (Vertex start_node = 1; start_node < G.N; ++start_node) {
            if (tin[start_node] != -1)
                continue;

            stack.push_back({start_node, V_NONE, -1, 0, 0});

            while (!stack.empty()) {
                DFSState& state = stack.back();

                if (state.neighbor_index == 0) {
                    if (tin[state.v] == -1) {
                        tin[state.v] = low[state.v] = timer++;
                    }
                }

                const auto& adj_v = G.adj[state.v];
                bool pushed_child = false;

                while (state.neighbor_index < adj_v.size()) {
                    const auto& edge = adj_v[state.neighbor_index];
                    Vertex to = edge.to;
                    state.neighbor_index++;

                    if (to == state.p)
                        continue;

                    if (forbidden_edge_ids && edge.id != -1 &&
                        edge.id <
                            static_cast<int32_t>(forbidden_edge_ids->size()) &&
                        (*forbidden_edge_ids)[edge.id]) {
                        continue;
                    }

                    if (tin[to] != -1) {

                        low[state.v] = min(low[state.v], tin[to]);
                        if (tin[to] < tin[state.v]) {
                            if (edge.id != -1) {
                                edge_stack.push_back(edge.id);
                            }
                        }
                    } else {

                        if (edge.id != -1) {
                            edge_stack.push_back(edge.id);
                        }

                        stack.push_back({to, state.v, edge.id, 0, 0});
                        pushed_child = true;
                        break;
                    }
                }

                if (pushed_child) {
                    continue;
                }

                Vertex v = state.v;
                Vertex p = state.p;

                int32_t edge_id_in = state.edge_id_in;
                int32_t children_count = state.children_count;
                stack.pop_back();

                if (p != V_NONE) {
                    DFSState& parent_state = stack.back();
                    parent_state.children_count++;

                    low[p] = min(low[p], low[v]);

                    if (low[v] >= tin[p]) {

                        if (parent_state.p != V_NONE) {
                            is_ap[p] = true;
                        }

                        int32_t bcc_index = BCCs.size();
                        vector<Vertex> component_vertices_with_dups;
                        int32_t critical_edge_id = edge_id_in;

                        while (!edge_stack.empty()) {
                            int32_t e_id = edge_stack.back();

                            bool is_critical = (e_id == critical_edge_id);

                            edge_stack.pop_back();

                            const OriginalEdge* e_ptr = G.get_edge_ptr(e_id);
                            if (e_ptr) {
                                component_vertices_with_dups.push_back(
                                    e_ptr->u);
                                component_vertices_with_dups.push_back(
                                    e_ptr->v);
                            }

                            if (e_id != -1 && e_id < static_cast<int32_t>(
                                                         edge_to_BCC.size())) {
                                edge_to_BCC[e_id] = bcc_index;
                            }

                            if (is_critical)
                                break;
                        }

                        if (!component_vertices_with_dups.empty()) {
                            vector<Vertex> component;
                            component.reserve(
                                component_vertices_with_dups.size());
                            stamp_counter_internal++;
                            for (Vertex u : component_vertices_with_dups) {
                                if (u < G.N && mark_v_internal[u] !=
                                                   stamp_counter_internal) {
                                    mark_v_internal[u] = stamp_counter_internal;
                                    component.push_back(u);

                                    if (u < static_cast<Vertex>(
                                                vertex_BCC_membership.size())) {

                                        vertex_BCC_membership[u].push_back(
                                            bcc_index);
                                    }
                                }
                            }
                            if (!component.empty()) {
                                BCCs.push_back(std::move(component));
                            }
                        }
                    }
                } else {

                    if (children_count > 1) {
                        is_ap[v] = true;
                    }
                }
            }
        }
    }

    inline bool is_in_BCC(int bcc_idx, Vertex v) const {
        if (v <= 0 || v >= G.N)
            return false;
        if (bcc_idx < 0 || bcc_idx >= static_cast<int32_t>(BCCs.size()))
            return false;

        const auto& memberships = vertex_BCC_membership[v];

        for (int32_t id : memberships) {
            if (id == bcc_idx)
                return true;
            if (id > bcc_idx)
                return false;
        }
        return false;
    }
};

class BCCFinder_Multi {
  public:
    const MultiGraph& MG;
    vector<int32_t> tin, low;
    int32_t timer;

    vector<vector<int32_t>> BCC_edges;
    vector<int32_t> edge_stack;

    BCCFinder_Multi(const MultiGraph& MG) : MG(MG) {}

    struct DFSState {
        Vertex v;
        Vertex p;
        int32_t parent_edge_id;
        size_t neighbor_index;
    };

    inline void find_BCCs() {

        timer = 0;
        tin.assign(MG.N, -1);
        low.assign(MG.N, -1);
        BCC_edges.clear();
        edge_stack.clear();

        vector<DFSState> stack;
        if (MG.N > 1)
            stack.reserve(MG.N);

        for (Vertex start_node = 1; start_node < MG.N; ++start_node) {
            if (tin[start_node] != -1)
                continue;

            if (MG.adj[start_node].empty())
                continue;

            stack.push_back({start_node, V_NONE, -1, 0});

            while (!stack.empty()) {
                DFSState& state = stack.back();

                if (state.neighbor_index == 0) {
                    if (tin[state.v] == -1) {
                        tin[state.v] = low[state.v] = timer++;
                    }
                }

                const auto& adj_v = MG.adj[state.v];
                bool pushed_child = false;

                while (state.neighbor_index < adj_v.size()) {
                    const auto& edge_info = adj_v[state.neighbor_index];
                    Vertex to = edge_info.first;
                    int32_t current_edge_id = edge_info.second;
                    state.neighbor_index++;

                    if (current_edge_id == state.parent_edge_id)
                        continue;

                    if (tin[to] != -1) {
                        low[state.v] = min(low[state.v], tin[to]);
                        if (tin[to] < tin[state.v]) {
                            edge_stack.push_back(current_edge_id);
                        }
                    } else {
                        edge_stack.push_back(current_edge_id);
                        stack.push_back({to, state.v, current_edge_id, 0});
                        pushed_child = true;
                        break;
                    }
                }

                if (pushed_child)
                    continue;

                Vertex v = state.v;
                Vertex p = state.p;
                int32_t parent_edge_id = state.parent_edge_id;
                stack.pop_back();

                if (p != V_NONE) {
                    low[p] = min(low[p], low[v]);

                    if (low[v] >= tin[p]) {
                        vector<int32_t> component;
                        while (!edge_stack.empty()) {
                            int32_t e_id = edge_stack.back();
                            edge_stack.pop_back();
                            component.push_back(e_id);

                            if (e_id == parent_edge_id)
                                break;
                        }
                        if (!component.empty()) {
                            BCC_edges.push_back(std::move(component));
                        }
                    }
                }
            }
        }
    }
};

struct BCTree {
    int32_t N;
    vector<vector<int32_t>> adj;

    int32_t get_ap_id(Vertex v) const { return v; }
    int32_t get_bcc_id(int32_t i) const { return N + i; }

    inline void build(const BCCFinder& bcc_finder, int32_t graph_N) {
        N = graph_N;
        const auto& BCCs = bcc_finder.BCCs;
        const auto& is_ap = bcc_finder.is_ap;

        int32_t total_nodes = N + BCCs.size();
        adj.clear();
        adj.resize(total_nodes);

        for (int32_t i = 0; i < static_cast<int32_t>(BCCs.size()); ++i) {
            int32_t bcc_id = get_bcc_id(i);

            for (Vertex v : BCCs[i]) {
                if (v < static_cast<int32_t>(is_ap.size()) && is_ap[v]) {
                    int32_t ap_id = get_ap_id(v);
                    adj[bcc_id].push_back(ap_id);
                    adj[ap_id].push_back(bcc_id);
                }
            }
        }
    }

    inline vector<int32_t> find_path(int32_t start_node, int32_t end_node) {

        if (start_node == -1 || end_node == -1)
            return {};
        if (start_node == end_node)
            return {start_node};
        int32_t total_nodes = adj.size();
        if (start_node >= total_nodes || end_node >= total_nodes ||
            start_node <= 0 || end_node <= 0)
            return {};

        queue<int32_t> q;
        vector<int32_t> parent(total_nodes, -1);
        q.push(start_node);
        parent[start_node] = 0;
        bool found = false;

        while (!q.empty()) {
            int32_t u = q.front();
            q.pop();
            if (u == end_node) {
                found = true;
                break;
            }
            for (const int v : adj[u]) {
                if (parent[v] == -1) {
                    parent[v] = u;
                    q.push(v);
                }
            }
        }

        if (!found)
            return {};

        vector<int32_t> path;
        int32_t curr = end_node;
        while (curr != 0) {
            path.push_back(curr);
            curr = parent[curr];
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

inline BoolVector compute_BAD_G(const Graph& G, Vertex S, Vertex T) {

    BCCFinder bcc_finder(G);
    bcc_finder.find_BCCs();
    BCTree bct;
    bct.build(bcc_finder, G.N);

    const auto& is_ap = bcc_finder.is_ap;
    const auto& BCCs = bcc_finder.BCCs;

    vector<int32_t> vertex_to_bcc(G.N, -1);
    for (int32_t i = 0; i < static_cast<int32_t>(BCCs.size()); ++i) {
        for (Vertex v : BCCs[i]) {
            if (v < G.N &&
                (v >= static_cast<int32_t>(is_ap.size()) || !is_ap[v])) {
                vertex_to_bcc[v] = i;
            }
        }
    }

    auto find_tau = [&](Vertex V) {
        if (V <= 0 || V >= G.N)
            return -1;
        if (V < static_cast<int32_t>(is_ap.size()) && is_ap[V]) {
            return bct.get_ap_id(V);
        } else {
            int32_t bcc_index = vertex_to_bcc[V];
            if (bcc_index != -1)
                return bct.get_bcc_id(bcc_index);
        }
        return -1;
    };

    int32_t S_tau = find_tau(S);
    int32_t T_tau = find_tau(T);
    vector<int32_t> path = bct.find_path(S_tau, T_tau);

    BoolVector is_bad(G.N, false);

    vector<int32_t> degrees_in_C_dat(G.N, 0);
    BoolVector in_C_ws(G.N, false);

    for (int32_t index = 0; index < static_cast<int32_t>(path.size());
         ++index) {
        const int32_t node_id = path[index];

        if (node_id >= G.N) {
            int32_t bcc_index = node_id - G.N;
            if (bcc_index < 0 || bcc_index >= static_cast<int32_t>(BCCs.size()))
                continue;

            const auto& C = BCCs[bcc_index];

            for (Vertex v : C) {
                if (v < G.N)
                    in_C_ws[v] = true;
            }

            for (Vertex u : C) {
                int32_t degree = 0;
                if (u < G.N) {
                    for (const auto& edge : G.adj[u]) {
                        if (edge.to < G.N && in_C_ws[edge.to])
                            degree++;
                    }
                    degrees_in_C_dat[u] = degree;
                }
            }

            for (Vertex u : C) {
                if (u == S || u == T || u >= G.N)
                    continue;

                if (degrees_in_C_dat[u] == 2) {

                    bool u_is_AP_connector = false;

                    if (u < static_cast<int32_t>(is_ap.size()) && is_ap[u]) {
                        int32_t u_ap_id = bct.get_ap_id(u);

                        if (index > 0 && path[index - 1] == u_ap_id) {
                            u_is_AP_connector = true;
                        }

                        if (!u_is_AP_connector &&
                            index < static_cast<int32_t>(path.size()) - 1 &&
                            path[index + 1] == u_ap_id) {
                            u_is_AP_connector = true;
                        }
                    }

                    if (!u_is_AP_connector) {
                        is_bad[u] = true;
                    }
                }
            }

            for (Vertex v : C) {
                if (v < G.N)
                    in_C_ws[v] = false;
            }
        }
    }
    return is_bad;
}

struct DSU {
    vector<int> fa, sz;
    DSU(int n = 0) { init(n); }
    void init(int n) {
        fa.resize(n);
        sz.assign(n, 1);
        std::iota(fa.begin(), fa.end(), 0);
    }

    int find(int x) {
        while (fa[x] != x) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }
        return x;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        if (sz[a] < sz[b])
            swap(a, b);
        fa[b] = a;
        sz[a] += sz[b];
    }
};

inline Path validate_separator(const vector<const OriginalEdge*>& R,
                               const Graph& G, bool required_odd_P_index,
                               const vector<int32_t>& P_indices,
                               const vector<int32_t>& min_P_neighbor_index,

                               vector<vector<pair<Vertex, int64_t>>>& adj_R_ws,
                               BoolVector& in_R_ws) {

    if (R.empty())
        return {};
    const int32_t N = G.N;

    vector<Vertex> vertices_R;
    vertices_R.reserve(R.size() + 1);

    for (const auto* edge_ptr : R) {
        Vertex u = edge_ptr->u;
        Vertex v = edge_ptr->v;
        int64_t w = edge_ptr->weight;
        if (u >= N || v >= N || u == 0 || v == 0)
            continue;

        adj_R_ws[u].push_back({v, w});
        adj_R_ws[v].push_back({u, w});

        if (!in_R_ws[u]) {
            in_R_ws[u] = true;
            vertices_R.push_back(u);
        }
        if (!in_R_ws[v]) {
            in_R_ws[v] = true;
            vertices_R.push_back(v);
        }
    }

    auto cleanup = [&]() {
        for (Vertex v : vertices_R) {
            in_R_ws[v] = false;
            adj_R_ws[v].clear();
        }
    };

    vector<Vertex> endpoints;
    for (Vertex v : vertices_R) {
        const auto& neighbors = adj_R_ws[v];
        if (neighbors.size() > 2) {
            cleanup();
            return {};
        }
        if (neighbors.size() == 1)
            endpoints.push_back(v);
    }

    if (endpoints.size() != 2) {
        cleanup();
        return {};
    }

    Path r;
    vector<int64_t> r_weights;
    r.reserve(R.size() + 1);
    r_weights.reserve(R.size());

    Vertex curr = endpoints[0];
    Vertex prev = V_NONE;

    while (curr != V_NONE) {
        r.push_back(curr);
        Vertex next = V_NONE;
        const auto& neighbors = adj_R_ws[curr];

        for (const auto& edge_info : neighbors) {
            Vertex neighbor = edge_info.first;
            int64_t weight = edge_info.second;
            if (neighbor != prev) {
                next = neighbor;
                r_weights.push_back(weight);
                break;
            }
        }
        prev = curr;
        curr = next;
    }

    cleanup();

    if (r.size() != R.size() + 1)
        return {};

    auto check_alignment = [&](const Path& path) {
        int32_t last_P_idx = -1;
        for (Vertex v : path) {
            if (v < static_cast<int32_t>(P_indices.size()) &&
                P_indices[v] != -1) {
                if (P_indices[v] <= last_P_idx)
                    return false;
                last_P_idx = P_indices[v];
            }
        }
        return true;
    };

    if (!check_alignment(r)) {
        reverse(r.begin(), r.end());
        reverse(r_weights.begin(), r_weights.end());
        if (!check_alignment(r))
            return {};
    }

    if (r.size() < 4)
        return {};

    for (size_t i = 2; i < r.size(); ++i) {
        if (r[i] >= static_cast<int32_t>(P_indices.size()) ||
            P_indices[r[i]] == -1)
            return {};
    }

    int32_t idx_r2 = P_indices[r[2]];
    if ((idx_r2 % 2 != 0) != required_odd_P_index)
        return {};

    if (!is_useful_weighted(r, r_weights, G))
        return {};

    Vertex r0 = r[0];
    bool traversable = false;

    if (r0 < static_cast<int32_t>(P_indices.size()) && P_indices[r0] != -1) {
        if (P_indices[r0] < idx_r2)
            traversable = true;
    }

    if (!traversable) {
        if (r0 < static_cast<int32_t>(min_P_neighbor_index.size()) &&
            min_P_neighbor_index[r0] != INF_INT) {

            if (min_P_neighbor_index[r0] < idx_r2)
                traversable = true;
        }
    }

    if (!traversable)
        return {};

    return r;
}

inline void compute_S_Separators(const Graph& G, const Path& P,
                                 vector<Path>& X_result) {

    if (P.empty())
        return;

    vector<int32_t> P_indices = get_P_indices_vec(P, G.N);
    vector<int32_t> min_P_neighbor_index(G.N, INF_INT);

    for (int32_t i = 0; i < static_cast<int32_t>(P.size()); ++i) {
        Vertex u = P[i];
        if (u >= G.N || u == 0)
            continue;
        if (i < min_P_neighbor_index[u])
            min_P_neighbor_index[u] = i;

        for (const auto& edge : G.adj[u]) {
            Vertex v = edge.to;
            if (v >= G.N || v == 0)
                continue;
            if (i < min_P_neighbor_index[v])
                min_P_neighbor_index[v] = i;
        }
    }

    BoolVector adj2;
    if (P.size() >= 3) {
        size_t n = P.size();
        adj2.resize(n - 2);
        for (size_t i = 0; i < n - 2; ++i) {
            adj2[i] = (get_edge_length(G, P[i], P[i + 2]) != INF);
        }
    }

    vector<vector<pair<Vertex, int64_t>>> adj_R_reusable(G.N);
    BoolVector in_R_reusable(G.N, false);

    int32_t max_id = G.max_edge_id;
    BoolVector in_C_edges_ws;
    if (max_id != -1) {
        in_C_edges_ws.resize(max_id + 1, false);
    }

    for (int parity_type = 0; parity_type < 2; ++parity_type) {
        bool find_odd_S_sep = (parity_type == 0);
        bool merge_even_P_indices = find_odd_S_sep;

        DSU dsu(G.N);

        if (P.size() >= 3) {
            for (int32_t i = 0; i <= static_cast<int32_t>(P.size()) - 3; ++i) {
                bool parity_match =
                    merge_even_P_indices ? (i % 2 == 0) : (i % 2 != 0);
                if (parity_match && adj2[i]) {
                    dsu.unite(P[i], P[i + 2]);
                }
            }
        }

        for (Vertex u = 1; u < G.N; ++u) {
            if (P_indices[u] != -1)
                continue;
            if (min_P_neighbor_index[u] == INF_INT)
                continue;

            int min_index = min_P_neighbor_index[u];

            for (const auto& edge : G.adj[u]) {
                Vertex v = edge.to;
                if (v >= G.N || v == 0)
                    continue;

                if (P_indices[v] != -1) {
                    int idx_v = P_indices[v];
                    bool parity_match = merge_even_P_indices ? (idx_v % 2 == 0)
                                                             : (idx_v % 2 != 0);

                    if (parity_match && idx_v > min_index) {
                        dsu.unite(u, v);
                    }
                }
            }
        }

        vector<int> deg_fat(G.N, 0);
        for (const auto* edge_ptr : G.edge_list) {
            Vertex u = edge_ptr->u, v = edge_ptr->v;
            if (u >= G.N || v >= G.N || u == 0 || v == 0)
                continue;
            int fu = dsu.find(u), fv = dsu.find(v);
            if (fu != fv) {
                deg_fat[fu]++;
                deg_fat[fv]++;
            }
        }

        vector<int32_t> old_to_new_id(G.N, 0);
        int32_t new_N = 1;

        for (Vertex i = 1; i < G.N; ++i) {
            if (deg_fat[i] > 0) {
                old_to_new_id[i] = new_N++;
            }
        }

        MultiGraph GMERGE(new_N);

        for (Vertex i = 1; i < G.N; ++i) {
            if (deg_fat[i] > 0) {
                int32_t new_id = old_to_new_id[i];
                if (new_id > 0 && new_id < new_N) {
                    GMERGE.adj[new_id].reserve(deg_fat[i]);
                }
            }
        }

        for (const auto* edge_ptr : G.edge_list) {
            Vertex u = edge_ptr->u;
            Vertex v = edge_ptr->v;
            if (u >= G.N || v >= G.N || u == 0 || v == 0)
                continue;
            int fu = dsu.find(u);
            int fv = dsu.find(v);

            if (fu != fv) {
                int32_t new_fu = old_to_new_id[fu];
                int32_t new_fv = old_to_new_id[fv];

                if (new_fu > 0 && new_fv > 0) {
                    int edge_id = edge_ptr->id;
                    GMERGE.adj[new_fu].push_back({new_fv, edge_id});
                    GMERGE.adj[new_fv].push_back({new_fu, edge_id});
                }
            }
        }

        BCCFinder_Multi bcc_finder(GMERGE);
        bcc_finder.find_BCCs();

        vector<Vertex> C_compact_vertices_vec;
        BoolVector in_C_compact_vertices_ws(new_N, false);

        for (const auto& C_edges : bcc_finder.BCC_edges) {
            C_compact_vertices_vec.clear();

            for (int32_t edge_id : C_edges) {
                if (edge_id >= 0 && edge_id <= max_id)
                    in_C_edges_ws[edge_id] = true;
            }

            for (int32_t edge_id : C_edges) {
                const OriginalEdge* edge_ptr = G.get_edge_ptr(edge_id);
                if (!edge_ptr)
                    continue;

                Vertex u = edge_ptr->u;
                Vertex v = edge_ptr->v;
                if (u >= G.N || v >= G.N || u == 0 || v == 0)
                    continue;

                Vertex compact_u = old_to_new_id[dsu.find(u)];
                Vertex compact_v = old_to_new_id[dsu.find(v)];

                if (compact_u != V_NONE &&
                    !in_C_compact_vertices_ws[compact_u]) {
                    in_C_compact_vertices_ws[compact_u] = true;
                    C_compact_vertices_vec.push_back(compact_u);
                }
                if (compact_v != V_NONE &&
                    !in_C_compact_vertices_ws[compact_v]) {
                    in_C_compact_vertices_ws[compact_v] = true;
                    C_compact_vertices_vec.push_back(compact_v);
                }
            }

            for (Vertex u_new : C_compact_vertices_vec) {

                if (u_new > 0 && u_new < GMERGE.N) {
                    vector<const OriginalEdge*> R;
                    R.reserve(GMERGE.adj[u_new].size());

                    for (const auto& edge_info : GMERGE.adj[u_new]) {
                        int edge_id = edge_info.second;

                        if (edge_id >= 0 && edge_id <= max_id &&
                            in_C_edges_ws[edge_id]) {
                            R.push_back(G.get_edge_ptr(edge_id));
                        }
                    }

                    Path r = validate_separator(R, G, find_odd_S_sep, P_indices,
                                                min_P_neighbor_index,
                                                adj_R_reusable, in_R_reusable);
                    if (!r.empty()) {
                        X_result.push_back(std::move(r));
                    }
                }
            }

            for (int32_t edge_id : C_edges) {
                if (edge_id >= 0 && edge_id <= max_id)
                    in_C_edges_ws[edge_id] = false;
            }

            for (Vertex v : C_compact_vertices_vec) {
                in_C_compact_vertices_ws[v] = false;
            }
        }
    }
}

inline vector<Path> compute_X_ST(const Graph& G, const Path& P) {
    vector<Path> X_ST_candidates;

    compute_S_Separators(G, P, X_ST_candidates);
    size_t X_S_size = X_ST_candidates.size();

    Path P_rev = P;
    reverse(P_rev.begin(), P_rev.end());

    compute_S_Separators(G, P_rev, X_ST_candidates);

    for (size_t i = X_S_size; i < X_ST_candidates.size(); ++i) {
        reverse(X_ST_candidates[i].begin(), X_ST_candidates[i].end());
    }

    return X_ST_candidates;
}

inline vector<Path> compute_X_EXTRA(const Graph& G, const Path& P0) {
    if (P0.empty())
        return {};

    vector<int64_t> P0_weights;
    if (!P0.empty()) {
        P0_weights.reserve(P0.size() - 1);
    }

    BoolVector is_edge_on_P0_vec;
    bool use_vec = (G.max_edge_id != -1);

    if (use_vec) {
        is_edge_on_P0_vec.resize(G.max_edge_id + 1, false);
    }

    for (size_t i = 0; i < P0.size() - 1; ++i) {
        Vertex u = P0[i], v = P0[i + 1];

        pair<int64_t, int32_t> info = G.get_edge_info(u, v);
        P0_weights.push_back(info.first);
        int32_t id = info.second;

        if (use_vec) {
            if (id != -1 &&
                id < static_cast<int32_t>(is_edge_on_P0_vec.size())) {
                is_edge_on_P0_vec[id] = true;
            } else if (id != -1) {

                use_vec = false;
                is_edge_on_P0_vec.clear();
                is_edge_on_P0_vec.shrink_to_fit();
            }
        }
    }

    OptimizedSet<PackedKey> edges_P0_set;
    if (!use_vec) {
        edges_P0_set.reserve(P0.size() - 1);
        for (size_t i = 0; i < P0.size() - 1; ++i) {
            edges_P0_set.insert(edge_key(P0[i], P0[i + 1]));
        }
    }

    vector<int32_t> component_id(G.N, 0);
    int comp_count = 0;
    queue<Vertex> q;

    for (Vertex v = 1; v < G.N; ++v) {
        if (component_id[v] == 0) {
            comp_count++;
            q.push(v);
            component_id[v] = comp_count;
            while (!q.empty()) {
                Vertex u = q.front();
                q.pop();
                for (const auto& edge : G.adj[u]) {
                    Vertex neighbor = edge.to;

                    bool on_P0 = false;
                    if (use_vec) {
                        if (edge.id != -1 &&
                            edge.id < static_cast<int32_t>(
                                          is_edge_on_P0_vec.size())) {
                            on_P0 = is_edge_on_P0_vec[edge.id];
                        }
                    } else {
                        on_P0 = edges_P0_set.count(edge_key(u, neighbor));
                    }

                    if (on_P0)
                        continue;

                    if (neighbor < G.N && component_id[neighbor] == 0) {
                        component_id[neighbor] = comp_count;
                        q.push(neighbor);
                    }
                }
            }
        }
    }

    vector<int32_t> BEL(P0.size());
    for (int32_t i = 0; i < static_cast<int32_t>(P0.size()); ++i) {
        if (P0[i] < G.N)
            BEL[i] = component_id[P0[i]];
    }

    vector<Path> X_EXTRA;
    int32_t i = 0;
    for (int32_t j = 1; j < static_cast<int32_t>(P0.size()); ++j) {
        if (j > 1 && BEL[j] != BEL[j - 2]) {
            if (i < j - 1) {
                Path candidate;
                vector<int64_t> candidate_weights;

                for (int32_t k = i; k <= j - 1; ++k) {
                    candidate.push_back(P0[k]);
                    if (k < j - 1)
                        candidate_weights.push_back(P0_weights[k]);
                }
                if (candidate.size() >= 4 &&
                    is_useful_weighted(candidate, candidate_weights, G)) {
                    X_EXTRA.push_back(std::move(candidate));
                }
            }
            i = j - 1;
        }
        if (j > 0 && BEL[j] == BEL[j - 1])
            i = j;
    }

    if (i < static_cast<int32_t>(P0.size()) - 1) {
        Path candidate;
        vector<int64_t> candidate_weights;
        for (int32_t k = i; k < static_cast<int32_t>(P0.size()); ++k) {
            candidate.push_back(P0[k]);
            if (k < static_cast<int32_t>(P0.size()) - 1)
                candidate_weights.push_back(P0_weights[k]);
        }
        if (candidate.size() >= 4 &&
            is_useful_weighted(candidate, candidate_weights, G)) {
            X_EXTRA.push_back(std::move(candidate));
        }
    }
    return X_EXTRA;
}

struct LR_Cache {

    mutable FlatMap L_cache;
    mutable FlatMap R_cache;
};

struct AVOID_precomputation {
    const Graph& G;
    const vector<Path>& X;

    vector<int32_t> inner_r_id;
    vector<int32_t> inner_idx;
    vector<uint8_t> on_r_endpoint;

    BoolVector is_edge_on_X;
    vector<uint8_t> is_X_head_edge;

    vector<vector<int32_t>> X_edge_ids;

    BCCFinder bcc_finder;

    vector<int32_t> head_rid_fwd;
    vector<int32_t> head_rid_rev;
    vector<Vertex> head_r2_fwd;
    vector<Vertex> head_r2_rev;

    LR_Cache lr_cache;

    AVOID_precomputation(const Graph& graph, const vector<Path>& paths)
        : G(graph), X(paths), bcc_finder(G) {

        inner_r_id.assign(G.N, -1);
        inner_idx.assign(G.N, -1);
        on_r_endpoint.assign(G.N, 0);

        int max_id = G.max_edge_id;
        if (max_id != -1) {
            is_edge_on_X.assign(max_id + 1, false);
            is_X_head_edge.assign(max_id + 1, 0);

            head_rid_fwd.assign(max_id + 1, -1);
            head_rid_rev.assign(max_id + 1, -1);
            head_r2_fwd.assign(max_id + 1, V_NONE);
            head_r2_rev.assign(max_id + 1, V_NONE);
        }

        X_edge_ids.resize(X.size());
        size_t total_edges_X = 0;

        for (int32_t r_id = 0; r_id < static_cast<int32_t>(X.size()); ++r_id) {
            const Path& r = X[r_id];
            if (r.empty())
                continue;

            if (r.size() > 1) {
                X_edge_ids[r_id].reserve(r.size() - 1);
                total_edges_X += r.size() - 1;
            }

            if (r.front() < G.N)
                on_r_endpoint[r.front()] |= 1;
            if (r.back() < G.N)
                on_r_endpoint[r.back()] |= 2;

            for (size_t i = 1; i < r.size() - 1; ++i) {
                if (r[i] < G.N) {
                    inner_r_id[r[i]] = r_id;
                    inner_idx[r[i]] = i;
                }
            }

            for (size_t i = 0; i < r.size() - 1; ++i) {
                int32_t edge_id = get_edge_id(G, r[i], r[i + 1]);
                X_edge_ids[r_id].push_back(edge_id);

                if (edge_id != -1 &&
                    edge_id < static_cast<int32_t>(is_edge_on_X.size())) {
                    is_edge_on_X[edge_id] = true;

                    if (i == 0) {
                        if (r[i] < r[i + 1])
                            is_X_head_edge[edge_id] |= 1;
                        else
                            is_X_head_edge[edge_id] |= 2;
                    }
                }
            }

            if (r.size() >= 3 && max_id != -1) {
                const auto& r_eids = X_edge_ids[r_id];

                int eid0 = r_eids[0];
                if (eid0 != -1 && eid0 <= max_id) {
                    if (r[0] < r[1]) {
                        head_rid_fwd[eid0] = r_id;
                        head_r2_fwd[eid0] = r[2];
                    } else {
                        head_rid_rev[eid0] = r_id;
                        head_r2_rev[eid0] = r[2];
                    }
                }

                int eidL = r_eids.back();
                if (eidL != -1 && eidL <= max_id) {
                    if (r[r.size() - 2] < r[r.size() - 1]) {
                        head_rid_rev[eidL] = r_id;
                        head_r2_rev[eidL] = r[r.size() - 3];
                    } else {
                        head_rid_fwd[eidL] = r_id;
                        head_r2_fwd[eidL] = r[r.size() - 3];
                    }
                }
            }
        }

        lr_cache.L_cache.init(total_edges_X * 2);
        lr_cache.R_cache.init(total_edges_X * 2);

        bcc_finder.forbidden_edge_ids = &is_edge_on_X;
        bcc_finder.find_BCCs();
    }

    inline bool is_inner(Vertex u) const {
        return u > 0 && u < G.N && inner_r_id[u] != -1;
    }
    inline int32_t get_r_id(Vertex u) const {
        return (u > 0 && u < G.N) ? inner_r_id[u] : -1;
    }
    inline int32_t get_idx_in_r(Vertex u) const {
        return (u > 0 && u < G.N) ? inner_idx[u] : -1;
    }

    inline bool is_on_r(Vertex node, int32_t r_id) const {
        if (r_id < 0 || r_id >= static_cast<int32_t>(X.size()))
            return false;

        if (is_inner(node) && get_r_id(node) == r_id)
            return true;

        const Path& r = X[r_id];
        return !r.empty() && (node == r.front() || node == r.back());
    }

    inline bool edge_on_X(int32_t edge_id) const {
        return edge_id != -1 &&
               edge_id < static_cast<int32_t>(is_edge_on_X.size()) &&
               is_edge_on_X[edge_id];
    }

    inline bool X_head(Vertex u, Vertex v, int32_t edge_id) const {
        if (edge_id != -1 &&
            edge_id < static_cast<int32_t>(is_X_head_edge.size())) {

            if (u < v) {
                return (is_X_head_edge[edge_id] & 1) != 0;
            } else {
                return (is_X_head_edge[edge_id] & 2) != 0;
            }
        }
        return false;
    }

    inline bool check_strong_connectivity(Vertex ri, Vertex u,
                                          int32_t edge_id_ri_u,
                                          Vertex target_v) const {

        bool edge_in_G_prime = !edge_on_X(edge_id_ri_u);

        if (edge_in_G_prime) {

            if (edge_id_ri_u != -1 &&
                edge_id_ri_u <
                    static_cast<int32_t>(bcc_finder.edge_to_BCC.size())) {
                int32_t bcc_idx = bcc_finder.edge_to_BCC[edge_id_ri_u];

                if (bcc_idx != -1 && bcc_finder.is_in_BCC(bcc_idx, target_v)) {
                    return true;
                }
            }
        } else {

            int32_t r_prime_id = -1;
            Vertex r_prime_2 = V_NONE;

            if (edge_id_ri_u != -1 &&
                edge_id_ri_u < static_cast<int32_t>(head_rid_fwd.size())) {
                if (ri < u) {
                    r_prime_id = head_rid_fwd[edge_id_ri_u];
                    r_prime_2 = head_r2_fwd[edge_id_ri_u];
                } else {
                    r_prime_id = head_rid_rev[edge_id_ri_u];
                    r_prime_2 = head_r2_rev[edge_id_ri_u];
                }
            }

            if (r_prime_id != -1 && r_prime_2 != V_NONE) {

                int32_t r_id = get_r_id(ri);
                if (r_id == -1)
                    return false;

                bool r_prime_2_on_r = false;
                const Path& r = X[r_id];
                for (Vertex v_in_r : r) {
                    if (v_in_r == r_prime_2) {
                        r_prime_2_on_r = true;
                        break;
                    }
                }

                if (r_prime_2_on_r) {

                    if (r_prime_2 == target_v) {
                        return true;
                    }
                } else {

                    int32_t chord_edge_id = get_edge_id(G, r_prime_2, ri);

                    if (chord_edge_id != -1 &&
                        chord_edge_id < static_cast<int32_t>(
                                            bcc_finder.edge_to_BCC.size())) {
                        int32_t bcc_idx = bcc_finder.edge_to_BCC[chord_edge_id];

                        if (bcc_idx != -1 &&
                            bcc_finder.is_in_BCC(bcc_idx, target_v)) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    inline Vertex get_L(int32_t r_id, Vertex u) const {
        if (r_id < 0 || r_id >= (int32_t)X.size() || u <= 0 || u >= G.N)
            return V_NONE;

        PackedKey key = lr_key(r_id, u);
        Vertex cached_val = lr_cache.L_cache.get(key);

        if (cached_val != V_NONE) {
            return cached_val;
        }

        const Path& r = X[r_id];
        Vertex L_val = V_NONE;

        for (int32_t i = 1; i < static_cast<int32_t>(r.size()) - 1; ++i) {
            Vertex ri = r[i];

            pair<int64_t, int32_t> edge_info = G.get_edge_info(ri, u);
            int32_t current_edge_id = edge_info.second;

            if (current_edge_id != -1) {
                L_val = ri;
                if (i >= 2) {
                    Vertex ri_minus_2 = r[i - 2];
                    if (check_strong_connectivity(ri, u, current_edge_id,
                                                  ri_minus_2)) {
                        L_val = ri_minus_2;
                    }
                }
                break;
            }
        }

        lr_cache.L_cache.emplace(key, L_val);
        return L_val;
    }

    inline Vertex get_R(int32_t r_id, Vertex u) const {
        if (r_id < 0 || r_id >= (int32_t)X.size() || u <= 0 || u >= G.N)
            return V_NONE;

        PackedKey key = lr_key(r_id, u);
        Vertex cached_val = lr_cache.R_cache.get(key);

        if (cached_val != V_NONE) {
            return cached_val;
        }

        const Path& r = X[r_id];
        Vertex R_val = V_NONE;

        for (int32_t i = 1; i < static_cast<int32_t>(r.size()) - 1; ++i) {
            Vertex ri = r[i];

            pair<int64_t, int32_t> edge_info = G.get_edge_info(ri, u);
            int32_t current_edge_id = edge_info.second;

            if (current_edge_id != -1) {
                R_val = ri;
                if (i <= static_cast<int32_t>(r.size()) - 3) {
                    Vertex ri_plus_2 = r[i + 2];
                    if (check_strong_connectivity(ri, u, current_edge_id,
                                                  ri_plus_2)) {
                        R_val = ri_plus_2;
                    }
                }
                break;
            }
        }

        lr_cache.R_cache.emplace(key, R_val);
        return R_val;
    }
};

inline Path AVOID(const Graph& G, Vertex S, Vertex T, const vector<Path>& X,
                  const BoolVector& is_bad) {

    AVOID_precomputation pre(G, X);

    using G1Node = pair<Vertex, int>;

    G1Node StartNode = {S, 0};
    G1Node EndNode = {T, 0};

    vector<array<int64_t, 2>> dist(G.N, {INF, INF});
    G1Node InvalidParent = {V_NONE, 0};
    vector<array<G1Node, 2>> parent(G.N, {InvalidParent, InvalidParent});

    using PQElementG1 = pair<int64_t, G1Node>;
    priority_queue<PQElementG1, vector<PQElementG1>, greater<PQElementG1>> pq;

    if (S >= G.N || T >= G.N || S == 0 || T == 0)
        return {};

    if (!is_bad.empty() && S < static_cast<int32_t>(is_bad.size()) && is_bad[S])
        return {};

    dist[S][0] = 0;
    pq.emplace(0, StartNode);
    int64_t shortest_dist = INF;

    while (!pq.empty()) {
        int64_t d = pq.top().first;
        G1Node u_node = pq.top().second;
        Vertex u = u_node.first;
        int32_t state_u = u_node.second;
        pq.pop();

        if (d > dist[u][state_u])
            continue;
        if (u_node == EndNode) {
            shortest_dist = d;
            break;
        }

        int32_t r_id_u = -1;
        const Path* r_u_ptr = nullptr;
        int32_t idx_u = -1;

        if (state_u == 1) {
            if (!pre.is_inner(u))
                continue;
            r_id_u = pre.get_r_id(u);
            if (r_id_u != -1) {
                r_u_ptr = &X[r_id_u];
                idx_u = pre.get_idx_in_r(u);
            }
        }

        for (const auto& edge : G.adj[u]) {
            Vertex v = edge.to;
            if (v >= G.N || v == 0)
                continue;

            int64_t w = edge.weight;
            int32_t edge_id = edge.id;

            if (!is_bad.empty() && v < static_cast<int32_t>(is_bad.size()) &&
                is_bad[v])
                continue;

            bool v_is_inner = pre.is_inner(v);

            auto try_transition = [&](int32_t state_v) {
                int64_t new_dist = d + w;
                if (new_dist < dist[v][state_v]) {
                    dist[v][state_v] = new_dist;
                    parent[v][state_v] = u_node;
                    pq.emplace(new_dist, G1Node{v, state_v});
                }
            };

            if (state_u == 0) {

                bool transition_to_high = false;
                if (v_is_inner) {
                    int32_t r_id_v = pre.get_r_id(v);
                    const Path& r_v = X[r_id_v];
                    int32_t idx_v = pre.get_idx_in_r(v);

                    if ((!pre.is_on_r(u, r_id_v) &&
                         idx_v == static_cast<int32_t>(r_v.size()) - 3) ||
                        (r_v.size() > 1 && u == r_v[0] && v == r_v[1])) {
                        transition_to_high = true;
                    }
                }
                if (transition_to_high) {
                    try_transition(1);
                }

                bool transition_to_low = true;

                if (pre.X_head(u, v, edge_id)) {
                    transition_to_low = false;
                }

                if (v_is_inner && transition_to_low) {
                    int32_t r_id_v = pre.get_r_id(v);

                    if (!pre.is_on_r(u, r_id_v) && pre.get_L(r_id_v, u) == v) {
                        transition_to_low = false;
                    }
                }
                if (transition_to_low) {
                    try_transition(0);
                }

            } else {

                if (r_u_ptr == nullptr)
                    continue;
                const Path& r_u = *r_u_ptr;

                if (v_is_inner) {
                    bool transition_high_high = true;
                    int32_t r_id_v = pre.get_r_id(v);

                    if (r_id_u == r_id_v) {

                        if (idx_u >= 1 && v == r_u[idx_u - 1])
                            transition_high_high = false;
                        if (idx_u >= 2 && v == r_u[idx_u - 2])
                            transition_high_high = false;
                    } else {

                        if (pre.get_R(r_id_u, v) == u)
                            transition_high_high = false;
                    }

                    if (transition_high_high) {
                        try_transition(1);
                    }
                }

                bool transition_high_low = true;

                if (pre.edge_on_X(edge_id))
                    transition_high_low = false;

                if (idx_u >= 2 && v == r_u[idx_u - 2])
                    transition_high_low = false;

                if (!pre.is_on_r(v, r_id_u) && pre.get_R(r_id_u, v) == u)
                    transition_high_low = false;

                if (v_is_inner) {
                    int32_t r_id_v = pre.get_r_id(v);

                    if (r_id_u != r_id_v && pre.get_L(r_id_v, u) == v)
                        transition_high_low = false;
                }

                if (transition_high_low) {
                    try_transition(0);
                }
            }
        }
    }

    if (shortest_dist == INF)
        return {};

    Path path_G;
    G1Node curr = EndNode;
    while (curr != StartNode) {
        path_G.push_back(curr.first);
        G1Node p = parent[curr.first][curr.second];
        if (p.first == V_NONE)
            break;
        curr = p;
    }
    if (curr == StartNode)
        path_G.push_back(StartNode.first);
    else
        return {};

    reverse(path_G.begin(), path_G.end());
    return path_G;
}

inline Path ShortestNonSeparatingPath(const Graph& G_input, Vertex S_original,
                                      Vertex T_original) {
    if (S_original == T_original)
        return {S_original};

    BridgeFinder bf(G_input);
    bf.find_Bridges();

    vector<int32_t> component_id(G_input.N, 0);
    int32_t comp_count = 0;

    vector<Vertex> stack;
    if (G_input.N > 1)
        stack.reserve(G_input.N);

    for (Vertex v = 1; v < G_input.N; ++v) {
        if (component_id[v] == 0) {
            comp_count++;
            stack.push_back(v);
            component_id[v] = comp_count;
            while (!stack.empty()) {
                Vertex u = stack.back();
                stack.pop_back();

                for (const auto& edge : G_input.adj[u]) {

                    if (edge.id != -1 &&
                        edge.id < static_cast<int32_t>(bf.is_bridge.size()) &&
                        bf.is_bridge[edge.id])
                        continue;

                    Vertex neighbor = edge.to;
                    if (neighbor < G_input.N && component_id[neighbor] == 0) {
                        component_id[neighbor] = comp_count;
                        stack.push_back(neighbor);
                    }
                }
            }
        }
    }

    if (S_original >= G_input.N || T_original >= G_input.N || S_original == 0 ||
        T_original == 0 ||
        component_id[S_original] != component_id[T_original] ||
        component_id[S_original] == 0) {
        return {};
    }

    int32_t target_comp = component_id[S_original];

    vector<Vertex> old_to_new_v(G_input.N, V_NONE);
    vector<Vertex> new_to_old_v;
    new_to_old_v.reserve(G_input.N);
    new_to_old_v.push_back(V_NONE);
    Vertex new_N_counter = 1;

    for (Vertex v = 1; v < G_input.N; ++v) {
        if (component_id[v] == target_comp) {
            old_to_new_v[v] = new_N_counter++;
            new_to_old_v.push_back(v);
        }
    }
    int32_t N_prime_count = new_N_counter - 1;

    int32_t M_prime_count = 0;
    vector<int32_t> degrees(N_prime_count + 1, 0);

    for (const auto* ptr : G_input.edge_list) {
        if (ptr->u < G_input.N && component_id[ptr->u] == target_comp &&
            ptr->v < G_input.N && component_id[ptr->v] == target_comp) {
            M_prime_count++;
            Vertex u_prime = old_to_new_v[ptr->u];
            Vertex v_prime = old_to_new_v[ptr->v];
            if (u_prime != V_NONE)
                degrees[u_prime]++;
            if (v_prime != V_NONE)
                degrees[v_prime]++;
        }
    }

    Graph G_prime(N_prime_count, M_prime_count);

    Vertex S_prime = old_to_new_v[S_original];
    Vertex T_prime = old_to_new_v[T_original];

    for (int32_t i = 1; i <= N_prime_count; ++i) {
        G_prime.adj[i].reserve(degrees[i]);
    }

    int32_t new_edge_id = 0;
    for (const auto* ptr : G_input.edge_list) {
        if (ptr->u < G_input.N && component_id[ptr->u] == target_comp &&
            ptr->v < G_input.N && component_id[ptr->v] == target_comp) {

            Vertex u_prime = old_to_new_v[ptr->u];
            Vertex v_prime = old_to_new_v[ptr->v];

            G_prime.add_edge(u_prime, v_prime, ptr->weight, new_edge_id++,
                             nullptr);
        }
    }

    G_prime.finalize_construction();

    const Graph& G = G_prime;
    Vertex S = S_prime;
    Vertex T = T_prime;

    BoolVector is_bad = compute_BAD_G(G, S, T);

    pair<int64_t, Path> result_P = dijkstra(G, S, T, is_bad);
    if (result_P.first == INF)
        return {};
    Path P = result_P.second;

    vector<Path> X_ST = compute_X_ST(G, P);

    vector<int32_t> P_indices = get_P_indices_vec(P, G.N);
    vector<int32_t> forbidden_ids_vec;
    int32_t max_id = -1;

    auto find_edge_id = [&](Vertex u, Vertex v) {
        return get_edge_id(G, u, v);
    };

    for (const Path& r : X_ST) {
        if (r.size() < 4)
            continue;

        bool is_S_sep = true;
        for (size_t i = 2; i < r.size(); ++i) {
            if (r[i] >= G.N || P_indices[r[i]] == -1) {
                is_S_sep = false;
                break;
            }
        }

        bool is_T_sep = true;
        for (size_t i = 0; i <= r.size() - 3; ++i) {
            if (r[i] >= G.N || P_indices[r[i]] == -1) {
                is_T_sep = false;
                break;
            }
        }

        if (is_S_sep) {
            int32_t id = find_edge_id(r[r.size() - 2], r[r.size() - 1]);
            if (id != -1) {
                forbidden_ids_vec.push_back(id);
                if (id > max_id)
                    max_id = id;
            }
        }
        if (is_T_sep) {
            int32_t id = find_edge_id(r[0], r[1]);
            if (id != -1) {
                forbidden_ids_vec.push_back(id);
                if (id > max_id)
                    max_id = id;
            }
        }
    }

    BoolVector G0_forbidden_edge_ids;
    if (max_id != -1) {
        G0_forbidden_edge_ids.resize(max_id + 1, false);
        for (int32_t id : forbidden_ids_vec)
            G0_forbidden_edge_ids[id] = true;
    }

    pair<int64_t, Path> result_P0 =
        dijkstra(G, S, T, is_bad, G0_forbidden_edge_ids);

    Path P0;
    if (result_P0.first != INF)
        P0 = result_P0.second;

    vector<Path> X_EXTRA = compute_X_EXTRA(G, P0);

    vector<Path> X_combined = std::move(X_ST);
    X_combined.reserve(X_combined.size() + X_EXTRA.size());

    X_combined.insert(X_combined.end(),
                      std::make_move_iterator(X_EXTRA.begin()),
                      std::make_move_iterator(X_EXTRA.end()));

    std::sort(X_combined.begin(), X_combined.end());
    X_combined.erase(std::unique(X_combined.begin(), X_combined.end()),
                     X_combined.end());

    const vector<Path>& X = X_combined;

    Path result_path_prime = AVOID(G, S, T, X, is_bad);

    if (result_path_prime.empty()) {
        return {};
    }

    Path result_path_original;
    result_path_original.reserve(result_path_prime.size());
    for (Vertex v_prime : result_path_prime) {
        if (v_prime > 0 &&
            v_prime < static_cast<int32_t>(new_to_old_v.size())) {
            result_path_original.push_back(new_to_old_v[v_prime]);
        } else {
            return {};
        }
    }

    return result_path_original;
}

constexpr int __buffsize = 1 << 20;
char __buff[__buffsize];
char *__buffs = __buff, *__buffe = __buff;

inline char getc() {
    if (__buffs == __buffe) {
        size_t flywheel = fread(__buff, 1, __buffsize, stdin);
        if (flywheel == 0)
            return EOF;
        __buffe = __buff + flywheel;
        __buffs = __buff;
    }
    return *(__buffs++);
}

template <typename T> inline void read_number(T& x) {
    x = 0;
    static char c;
    bool flag = false;

    while ((c = getc()) != EOF && (c < '0' || c > '9') && c != '-')
        ;

    if (c == EOF)
        return;

    if (c == '-') {
        flag = true;
        c = getc();
    } else if (c >= '0' && c <= '9') {
        x = c - '0';
        c = getc();
    }

    while (c != EOF && c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c - '0');
        c = getc();
    }
    if (flag)
        x = -x;
}

inline void read_int(int32_t& x) { read_number<int32_t>(x); }
inline void read_long(int64_t& x) { read_number<int64_t>(x); }

int main() {

    ios_base::sync_with_stdio(false);

    int32_t n, m;
    read_int(n);
    read_int(m);

    struct InputEdge {
        PackedKey key;
        int64_t w;
        bool operator<(const InputEdge& other) const {
            if (key != other.key)
                return key < other.key;
            return w < other.w;
        }
    };
    vector<InputEdge> input_edges;
    if (m > 0)
        input_edges.reserve(m);

    for (int32_t i = 0; i < m; ++i) {
        int32_t u, v;
        int64_t w;
        read_int(u);
        read_int(v);
        read_long(w);
        if (u != v) {
            PackedKey key = edge_key(u, v);
            input_edges.push_back({key, w});
        }
    }

    sort(input_edges.begin(), input_edges.end());

    int32_t s, t;
    read_int(s);
    read_int(t);

    int32_t unique_edge_count = 0;
    vector<int32_t> degrees(n + 1, 0);

    if (!input_edges.empty()) {
        unique_edge_count = 1;
        auto count_degree = [&](const InputEdge& edge) {
            pair<Vertex, Vertex> uv = unpack_edge_key(edge.key);
            if (uv.first <= n)
                degrees[uv.first]++;
            if (uv.second <= n)
                degrees[uv.second]++;
        };

        count_degree(input_edges[0]);
        for (size_t i = 1; i < input_edges.size(); ++i) {
            if (input_edges[i].key != input_edges[i - 1].key) {
                unique_edge_count++;
                count_degree(input_edges[i]);
            }
        }
    }

    Graph G(n, unique_edge_count);

    for (int32_t i = 1; i <= n && i < G.N; ++i) {
        G.adj[i].reserve(degrees[i]);
    }

    int32_t edge_id_counter = 0;

    if (!input_edges.empty()) {
        auto add_edge_to_G = [&](const InputEdge& edge) {
            pair<Vertex, Vertex> uv = unpack_edge_key(edge.key);
            int64_t w = edge.w;
            int32_t id = edge_id_counter++;

            G.add_edge(uv.first, uv.second, w, id, nullptr);
        };

        add_edge_to_G(input_edges[0]);
        for (size_t i = 1; i < input_edges.size(); ++i) {
            if (input_edges[i].key != input_edges[i - 1].key) {
                add_edge_to_G(input_edges[i]);
            }
        }
    }

    G.finalize_construction();

    Path result = ShortestNonSeparatingPath(G, s, t);

    if (result.empty()) {

        printf("-1\n");
    } else {
        int64_t total_weight = 0;
        for (size_t i = 0; i < result.size() - 1; ++i) {

            total_weight += get_edge_length(G, result[i], result[i + 1]);
        }
        printf("%lld\n", (long long)total_weight);
    }

    return 0;
}