#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100005
#define MAXM 200005
#define MAXS (MAXN + MAXM + 1)
#define LN 20
#define INF 1000000007
struct Edge {
int a, b, weight;
bool operator<(const Edge &other) const {
return weight < other.weight;
}
};
struct DSU {
vector<int> parent;
vector<int> sizes;
int getRoot(int node) {
if(node == parent[node]) {
return node;
}
return parent[node] = getRoot(parent[node]);
}
DSU(int n) {
parent.resize(n);
sizes.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
sizes[i] = 1;
}
}
DSU() {}
};
int n, m;
bool swappable[MAXS];
int nodeweight[MAXS];
int indegree[MAXN];
vector<int> krtadj[MAXS];
Edge edges[MAXM];
int up[MAXS][LN];
int depth[MAXS];
DSU dsu;
int krtsize, krtnode;
void dfs(int node, int par, int dep) {
depth[node] = dep;
for(auto next : krtadj[node]) {
if(next != par) {
up[0][next] = node;
dfs(next, node, dep + 1);
}
}
}
int LCA(int a, int b) {
// cout << "depth of " << a << ", " << b << ": ";
// cout << depth[a] << " " << depth[b] << endl;
if(depth[a] < depth[b]) {
swap(a, b);
}
for(int i = LN - 1; i >= 0; --i) {
if(depth[up[i][a]] >= depth[b]) {
// cout << "a" << endl;
a = up[i][a];
}
}
// cout << "same depth" << endl;
if (a == b) {
return a;
}
for(int i = LN - 1; i >= 0; --i) {
if(up[i][a] != up[i][b]) {
a = up[i][a];
a = up[i][b];
}
}
// cout << "done" << endl;
return up[0][a];
}
void init(int32_t _n, int32_t _m, vector<int32_t> u, vector<int32_t> v, vector<int32_t> w) {
n = _n;
m = _m;
for(int i = 0; i < m; ++i) {
edges[i] = {u[i] + 1, v[i] + 1, w[i]};
}
sort(edges, edges + m);
krtsize = n + m + 1;
krtnode = n + 1;
dsu = DSU(krtsize);
// cout << "finsiehd init dsu" << endl;
for(int i = 0; i < m; ++i) {
Edge edge = edges[i];
int a = edge.a; int b = edge.b; int weight = edge.weight;
++indegree[a]; ++indegree[b];
// cout << "finished reading in edges" << endl;
int aroot = dsu.getRoot(a);
int broot = dsu.getRoot(b);
// cout << "finished getting root" << endl;
if(aroot == broot) {
// cout << "merging same component" << endl;
if(!swappable[aroot]) {
swappable[aroot] = true;
nodeweight[aroot] = weight;
}
}
else {
// cout << "different components" << endl;
// cout << "nodes: " << a << " " << b << endl;
// cout << "roots: " << aroot << " " << broot << endl;
krtadj[krtnode].push_back(aroot);
krtadj[krtnode].push_back(broot);
nodeweight[krtnode] = weight;
if(indegree[a] > 2 || indegree[b] > 2 || swappable[aroot] || swappable[broot]) {
swappable[krtnode] = true;
}
// cout << "merging" << endl;
dsu.parent[aroot] = krtnode;
dsu.parent[broot] = krtnode;
// cout << "finished merging" << endl;
++krtnode;
}
}
// cout << "finished constructing krt" << endl;
depth[0] = INF;
dfs(krtnode - 1, -1, 0);
for(int i = 1; i < LN; ++i) {
for(int j = 1; j <= krtsize; ++j) {
up[i][j] = up[i - 1][up[i - 1][j]];
}
}
// cout << "finished init for lca" << endl;
}
int getMinimumFuelCapacity(int32_t x, int32_t y) {
++x; ++y;
int closestswappable = LCA(x, y);
// cout << "got lca" << endl;
if(swappable[closestswappable]) {
// cout << "lca was swappable" << endl;
return nodeweight[closestswappable];
}
for(int i = LN - 1; i >= 0; --i) {
int ancestor = up[i][closestswappable];
if(ancestor != 0 && !swappable[ancestor]) {
closestswappable = ancestor;
}
}
// cout << "found one lower" << endl;
closestswappable = up[0][closestswappable];
if(swappable[closestswappable]) {
return nodeweight[closestswappable];
}
return -1;
}
// signed main() {
// int n, m;
// cin >> n >> m;
// vector<int> u(m);
// vector<int> v(m);
// vector<int> w(m);
// for(int i = 0; i < m; ++i) {
// cin >> u[i] >> v[i] >> w[i];
// }
// init(n, m, u, v, w);
// int q;
// cin >> q;
// while(q--) {
// int a, b;
// cin >> a >> b;
// cout << getMinimumFuelCapacity(a, b) << endl;
// }
// }
