#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
bool operator<(const Edge &o) const {
return w < o.w;
}
};
struct Node {
int parent, size;
int deg; // bậc của node
int cnt0, cnt1; // số node bậc 1 và bậc 2 trong component nếu là root
int l, r;
};
struct PersistentDSU {
int n;
vector<int> root; // root[version]
vector<Node> seg;
PersistentDSU(int n_) : n(n_) {
seg.reserve(40 * n); // phòng đủ bộ nhớ
int initRoot = build(1, n);
root.push_back(initRoot);
}
int build(int l, int r) {
int id = seg.size();
seg.push_back({});
if (l == r) {
seg[id].parent = l;
seg[id].size = 1;
seg[id].deg = 0;
seg[id].cnt0 = 0;
seg[id].cnt1 = 0;
return id;
}
int mid = (l + r) / 2;
seg[id].l = build(l, mid);
seg[id].r = build(mid+1, r);
return id;
}
Node query(int id, int l, int r, int pos) {
if (l == r) return seg[id];
int mid = (l + r) / 2;
if (pos <= mid) return query(seg[id].l, l, mid, pos);
else return query(seg[id].r, mid+1, r, pos);
}
int update(int prev, int l, int r, int pos, Node val) {
int id = seg.size();
seg.push_back(seg[prev]); // copy node
if (l == r) {
seg[id] = val;
return id;
}
int mid = (l + r) / 2;
if (pos <= mid) seg[id].l = update(seg[prev].l, l, mid, pos, val);
else seg[id].r = update(seg[prev].r, mid+1, r, pos, val);
return id;
}
int find(int rootId, int u) {
Node nu = query(rootId, 1, n, u);
if (nu.parent == u) return u;
return find(rootId, nu.parent);
}
int unionSet(int rootId, int u, int v) {
u = find(rootId, u);
v = find(rootId, v);
if (u == v) return rootId;
Node nu = query(rootId, 1, n, u);
Node nv = query(rootId, 1, n, v);
if (nu.size < nv.size) swap(u, v), swap(nu, nv);
// v -> u
nv.parent = u;
int newRoot = update(rootId, 1, n, v, nv);
nu.size += nv.size;
nu.cnt0 += nv.cnt0;
nu.cnt1 += nv.cnt1;
newRoot = update(newRoot, 1, n, u, nu);
return newRoot;
}
int incDeg(int rootId, int u) {
Node nu = query(rootId, 1, n, u);
int r = find(rootId, u);
Node nr = query(rootId, 1, n, r);
if (nu.deg == 1) nr.cnt0--; // bậc 1 -> 2
if (nu.deg == 0) nr.cnt0++;
if (nu.deg == 1) nr.cnt1++;
nu.deg++;
rootId = update(rootId, 1, n, u, nu);
rootId = update(rootId, 1, n, r, nr);
return rootId;
}
// check điều kiện Hamilton path component chứa x,y
bool check(int rootId, int x, int y) {
int rx = find(rootId, x);
int ry = find(rootId, y);
if (rx != ry) return false;
Node nr = query(rootId, 1, n, rx);
return !(nr.cnt1 == nr.size - 2 && nr.cnt0 == 2);
}
};
int n, m, q;
vector<Edge> edges;
PersistentDSU *dsu;
vector<int> versionRoot;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N; m = M;
edges.resize(m);
for (int i = 0; i < m; i++) {
edges[i] = {U[i]+1, V[i]+1, W[i]}; // shift sang 1-based
}
sort(edges.begin(), edges.end());
dsu = new PersistentDSU(n);
versionRoot.resize(m+1);
versionRoot[0] = dsu->root[0];
for (int i = 1; i <= m; i++) {
int rootId = versionRoot[i-1];
rootId = dsu->incDeg(rootId, edges[i-1].u);
rootId = dsu->incDeg(rootId, edges[i-1].v);
rootId = dsu->unionSet(rootId, edges[i-1].u, edges[i-1].v);
versionRoot[i] = rootId;
}
}
int getMinimumFuelCapacity(int X, int Y) {
X++, Y++;
int l = 1, r = m, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (dsu->check(versionRoot[mid], X, Y)) {
ans = edges[mid-1].w;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
