#include "swap.h" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back typedef long long ll; typedef pair<int, int> pi; typedef vector<int> vi; typedef vector<ll> vl; typedef tuple<int, int, int> ti; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #ifdef LOCAL #include <debug.h> #else #define debug(...) #define debugArr(...) #endif const int MOD = 1000000007; const char nl = '\n'; const int N = 1e5; const int inf = 2e9; int par[N], comp_size[N], merged[N], time_valid[N], deg[N]; int find(int a) { while (par[a] != a) a = par[a]; return a; } void join(int a, int b, int time) { deg[a]++; deg[b]++; bool athree = deg[a] >= 3; bool bthree = deg[b] >= 3; a = find(a); b = find(b); if (athree) time_valid[a] = min(time_valid[a], time); if (bthree) time_valid[b] = min(time_valid[b], time); if (a == b) { time_valid[a] = min(time_valid[a], time); return; } if (comp_size[a] < comp_size[b]) swap(a, b); // cout << b << " into " << a << nl; time_valid[a] = min(time_valid[a], max(time, time_valid[b])); par[b] = a; comp_size[a] += comp_size[b]; merged[b] = time; } void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < n; i++) { comp_size[i] = 1; par[i] = i; time_valid[i] = inf; merged[i] = 0; } vector<int> edges(m); iota(edges.begin(), edges.end(), 0); sort(edges.begin(), edges.end(), [&] (auto &a, auto &b) { return W[a] < W[b]; }); for (int &i: edges) { int u = U[i]; int v = V[i]; int w = W[i]; join(u, v, w); } } int getMinimumFuelCapacity(int X, int Y) { // ans is max(min(valid on path to root), max(merge on path to lca)) int merge_time = 0; int valid_time = inf; if (find(X) != find(Y)) return -1; int x = X; int y = Y; while(x != y) { // debug(x, y); if (comp_size[x] > comp_size[y]) swap(x, y); valid_time = min(valid_time, max(merge_time, time_valid[x])); merge_time = max(merge_time, merged[x]); x = par[x]; } // debug(x, time_valid[4]); // debug(merge_time, valid_time); int ans = merge_time; while(merged[x] != 0) { valid_time = min(valid_time, max(merge_time, time_valid[x])); merge_time = max(merge_time, merged[x]); x = par[x]; } valid_time = min(valid_time, max(merge_time, time_valid[x])); ans = max(ans, valid_time); if (ans == inf) return -1; return ans; } // struct UF { // vi id, valid, degg; // UF (int n): id(n), valid(n), degg(n) { // iota(all(id), 0); // } // int find(int a) { // if (id[a] == a) return a; // return id[a] = find(id[a]); // } // void join(int a, int b) { // degg[a]++; degg[b]++; // bool v = (degg[a] >= 3 || degg[b] >= 3); // a = find(a); // b = find(b); // if (a == b) { // valid[a] = 1; // return; // } // id[b] = a; // valid[a] |= v | valid[b]; // } // }; // int main() { // int n, m, q; cin >> n >> m >> q; // vector<ti> edges; // vi A, B, W; // rep(i, 0, m) { // int a, b, c; cin >> a >> b >> c; // A.pb(a); // B.pb(b); // W.pb(c); // edges.pb({c, a, b}); // } // init(n, m, A, B, W); // sort(all(edges)); // while(q--) { // int a, b; cin >> a >> b; // UF uf(n); // int ans = -1; // for (auto &[c, u, v]: edges) { // // debug(c, u, v); // uf.join(u, v); // if (uf.find(a) == uf.find(b) && uf.valid[uf.find(a)]) { // ans = c; // break; // } // } // cout << ans << " " << getMinimumFuelCapacity(a, b) << nl; // assert(ans == getMinimumFuelCapacity(a, b)); // } // }