#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
class DisjointSet {
private:
vector<int> lab;
public:
DisjointSet(int _n = 0) {
lab.assign(_n + 7, -1);
}
int find(int u) {
return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
}
bool join(int u, int v) {
u = find(u), v = find(v);
if(u == v)
return (false);
if(lab[u] > lab[v])
swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return (true);
}
int getSize(int u) {
return -lab[find(u)];
}
} dsu;
struct Edge {
int u, v, w;
} edge[2 * MAXN];
struct SegNode {
int cnt, L, R;
} seg[100 * MAXN];
vector<int> idw;
vector<ii> adj[MAXN];
int version[MAXN], tIn[MAXN], tOut[MAXN], tour[MAXN], depth[MAXN], P[MAXN][17], Pw[MAXN][17];
int deg[MAXN], pa[MAXN], cntLeaf[MAXN], tmp[MAXN], maxw, nTree, numNode, numEdge;
bool dp[1003][1003], dx[MAXN], hasChild[MAXN], check_sub1, check_sub2;
int cntTime(0);
void preDfs(int u) {
tIn[u] = ++cntTime;
tour[cntTime] = u;
++tmp[tIn[u]];
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi), id(adj[u][it].se);
if(v != P[u][0]) {
depth[v] = depth[u] + 1;
P[v][0] = u;
Pw[v][0] = id;
preDfs(v);
--tmp[tIn[u]];
}
}
tOut[u] = cntTime;
}
int lca(int u, int v) {
if(depth[u] < depth[v])
swap(u, v);
for (int i1 = depth[u] - depth[v]; i1 > 0; i1 ^= i1 & -i1) {
int i = __builtin_ctz(i1);
u = P[u][i];
}
if(u == v)
return u;
for (int i = 31 - __builtin_clz(depth[u]); i >= 0; --i) {
if(P[u][i] != P[v][i])
u = P[u][i], v = P[v][i];
}
return P[u][0];
}
int build(int l, int r, int tmp[]) {
if(l == r) {
seg[++nTree].cnt = tmp[l];
return nTree;
}
int cur(++nTree), mid = (l + r) >> 1;
seg[cur].L = build(l, mid, tmp);
seg[cur].R = build(mid + 1, r, tmp);
seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt;
return cur;
}
int update(int oldID, int l, int r, int pos, int val) {
if(l == r) {
seg[++nTree] = seg[oldID];
seg[nTree].cnt += val;
return nTree;
}
int cur(++nTree), mid = (l + r) >> 1;
seg[cur] = seg[oldID];
if(pos <= mid) {
seg[cur].L = update(seg[oldID].L, l, mid, pos, val);
} else {
seg[cur].R = update(seg[oldID].R, mid + 1, r, pos, val);
}
seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt;
return cur;
}
int query(int id, int l, int r, int u, int v) {
if(u <= l && r <= v)
return seg[id].cnt;
int mid = (l + r) >> 1, res(0);
if(mid >= u)
res += query(seg[id].L, l, mid, u, v);
if(mid + 1 <= v)
res += query(seg[id].R, mid + 1, r, u, v);
return res;
}
void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W) {
numNode = _N, numEdge = _M;
for (int i = 0; i < numEdge; ++i) {
edge[i] = {_U[i], _V[i], _W[i]};
maxw = max(maxw, edge[i].w);
++deg[edge[i].u], ++deg[edge[i].v];
}
check_sub1 = 1;
for (int i = 0; i < numNode; ++i)
check_sub1 &= (deg[i] <= 2);
sort(edge, edge + numEdge, [](const Edge &a, const Edge &b) {
return (a.w < b.w);
});
dsu = DisjointSet(numNode);
int cnt(0);
for (int i = 0; i < numEdge; ++i) {
int u(edge[i].u), v(edge[i].v);
if(dsu.join(u, v)) {
adj[u].push_back(ii(v, cnt));
adj[v].push_back(ii(u, cnt));
idw.push_back(edge[i].w);
++cnt;
}
}
P[0][0] = -1, depth[0] = 1;
preDfs(0);
for (int j = 1; (1 << j) <= numNode; ++j) {
for (int i = 0; i < numNode; ++i) {
if(P[i][j - 1] == -1) {
P[i][j] = -1;
} else {
P[i][j] = P[P[i][j - 1]][j - 1];
Pw[i][j] = max(Pw[i][j - 1], Pw[P[i][j - 1]][j - 1]);
}
}
}
version[0] = build(1, numNode, tmp);
cnt = 0;
dsu = DisjointSet(numNode);
for (int i = 0; i < numEdge; ++i) {
int u(edge[i].u), v(edge[i].v);
if(dsu.find(u) != dsu.find(v)) {
if(P[u][0] == v)
swap(u, v);
++cnt;
int qr = query(version[cnt - 1], 1, numNode, tIn[v], tOut[v]) - (!hasChild[u]);
version[cnt] = update(version[cnt - 1], 1, numNode, tIn[u], qr);
int w(u);
for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) {
if(P[w][i] != -1 && dsu.find(P[w][i]) == dsu.find(u))
w = P[w][i];
}
w = P[w][0];
if(w != -1)
version[cnt] = update(version[cnt], 1, numNode, tIn[w], -qr);
dsu.join(u, v);
hasChild[u] = 1;
/*cout << u << ' ' << v << ": ";
for (int i = 0; i < numNode; ++i)
cout << query(version[cnt], 1, numNode, tIn[i], tOut[i]) << ' '; cout << '\n';*/
}
}
}
ii dfs(int u) {
dx[u] = 1;
cntLeaf[u] = 0;
ii res = {sz(adj[u]), 1};
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi);
if(!dx[v]) {
pa[v] = u;
ii tmp = dfs(v);
res = {res.fi + tmp.fi, res.se + tmp.se};
cntLeaf[u] += cntLeaf[v];
}
}
if(cntLeaf[u] == 0)
cntLeaf[u] = 1;
return res;
}
int sub4(int x, int y) {
int l(0), r(numEdge - 1), ans(-1);
while(l <= r) {
int mid = (l + r) >> 1;
for (int i = 0; i < numNode; ++i) {
adj[i].clear();
dx[i] = 0;
}
for (int i = 0; i <= mid; ++i) {
int u(edge[i].u), v(edge[i].v);
adj[u].push_back(ii(v, 0));
adj[v].push_back(ii(u, 0));
}
pa[x] = -1;
ii res = dfs(x);
bool check(0);
if(dx[y]) {
int u(y);
while(pa[u] != x)
u = pa[u];
check = (res.fi / 2 >= res.se || cntLeaf[y] > 1 || cntLeaf[x] - cntLeaf[u] > 1 || cntLeaf[u] - cntLeaf[y] > 0);
}
if(check) {
ans = edge[mid].w;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int sub5(int x, int y) {
int l(0), r(numNode - 1), ans(-1);
int par = lca(x, y);
int tmp(x);
for (int i1 = depth[x] - depth[par]; i1 > 0; i1 ^= i1 & -i1) {
int i = __builtin_ctz(i1);
l = max(l, Pw[tmp][i]);
tmp = P[tmp][i];
}
tmp = y;
for (int i1 = depth[y] - depth[par]; i1 > 0; i1 ^= i1 & -i1) {
int i = __builtin_ctz(i1);
l = max(l, Pw[tmp][i]);
tmp = P[tmp][i];
}
if(par == y)
swap(x, y);
int c(-1);
if(par == x) {
c = y;
for (int i1 = depth[y] - depth[x] - 1; i1 > 0; i1 ^= i1 & -i1) {
int i = __builtin_ctz(i1);
c = P[c][i];
}
}
while(l <= r) {
int mid = (l + r) >> 1;
bool check(0);
if(par == x) {
int w(x);
for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) {
if(P[w][i] != -1 && Pw[w][i] <= mid)
w = P[w][i];
}
int cntLeafc = query(version[mid + 1], 1, numNode, tIn[c], tOut[c]);
int cntLeafx = query(version[mid + 1], 1, numNode, tIn[w], tOut[w]) - cntLeafc;
int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
int cntLeafInPath = cntLeafc - cntLeafy;
//cout << '\n' << x << ' ' << y << ' ' << w << ' ' << c << ' ' << mid << ' ' << cntLeafc << ' ' << cntLeafx << ' ' << cntLeafy << ' ' << cntLeafInPath << '\n';
check = (cntLeafx > 1 || cntLeafy > 1 || cntLeafInPath > 0);
} else {
if(par > 0 && Pw[par][0] <= mid) {
check = 1;
} else {
int cntLeafx = query(version[mid + 1], 1, numNode, tIn[x], tOut[x]);
int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
int cntLeafInPath = query(version[mid + 1], 1, numNode, tIn[par], tOut[par]) - cntLeafx - cntLeafy;
check = (cntLeafx > 1 || cntLeafy > 1 || cntLeafInPath > 0);
}
}
if(check) {
ans = idw[mid];
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int getMinimumFuelCapacity(int x, int y) {
if(check_sub1)
return (numNode == numEdge) ? maxw : -1;
/*if(sub5(x, y) != sub4(x, y))
exit(1);*/
if(numEdge == numNode - 1)
return sub5(x, y);
return sub4(x, y);
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "swap"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _U, _V, _W;
int _N, _M, _Q;
cin >> _N >> _M >> _Q;
_U.resize(_M), _V.resize(_M), _W.resize(_M);
for (int i = 0; i < _M; ++i) {
cin >> _U[i] >> _V[i] >> _W[i];
_U[i] = Random(0, i), _V[i] = i + 1, _W[i] = Random(1, 1e5); cout << _U[i] << ' ' << _V[i] << ' ' << _W[i] << '\n';
}
init(_N, _M, _U, _V, _W);
for (int t = 0; t < _Q; ++t) {
int _X, _Y;
cin >> _X >> _Y;
_X = Random(0, _N - 2), _Y = Random(_X + 1, _N - 1);
cout << "MINIMUM FUEL CAPACITY " << _X << " TO " << _Y << ": " << getMinimumFuelCapacity(_X, _Y) << '\n';
}
return 0;
}
#endif // Nhoksocqt1
