#include "swap.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define L(i, j, k) for (int i = (j); i <= k; i++)
#define R(i, j, k) for (int i = (j); i >= k; i--)
struct dsu {
vector<int> fa, sz;
vector<bool> ok;
dsu(int n) {
fa.resize(n + 10);
iota(fa.begin(), fa.end(), 0);
sz.assign(n + 10, 1);
ok.assign(n + 10, false);
}
int find(int x) {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
bool merge(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (sz[py] > sz[px]) swap(px, py);
sz[px] += sz[py]; fa[py] = px;
ok[px] = ok[px] || ok[py];
return true;
}
bool same(int x, int y) {
int px = find(x), py = find(y);
return px == py;
}
};
const int nax = 100050;
int N, M;
vector<pair<int, int>> G[nax];
vector<pair<int, pair<int, int>>> edges;
void init(int _N, int _M, std::vector<int> _U, std::vector<int> _V, std::vector<int> _W) {
N = _N; M = _M;
L(i, 0, M - 1) edges.push_back(make_pair(_W[i], make_pair(_U[i], _V[i])));
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
// in order to speed up,
// we want to check connectivity, cycle, and whether the degree >= 3
dsu D(N);
vector<int> deg(N);
for (int i = 0; i < edges.size(); i++) {
int w = edges[i].first;
int u = edges[i].second.first, v = edges[i].second.second;
if (D.same(u, v)) D.ok[D.find(u)] = true; // cycle is formed
deg[u]++; deg[v]++;
if (deg[u] >= 3) D.ok[D.find(u)] = true; // degree >= 3
if (deg[v] >= 3) D.ok[D.find(v)] = true; // degree >= 3
D.merge(u, v); // merge them
if (D.same(X, Y) && D.ok[D.find(X)] == true) // if they are in the same component and its ok to swap them
return w;
}
return -1;
}
