#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int INF{1 << 30};
vector<int> p, p_w, sz, l_w;
int find(int i, int w) {
while(p_w[i] <= w) i = p[i];
return i;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
p = vector<int>(N), iota(p.begin(), p.end(), 0);
p_w = vector<int>(N, INF);
sz = vector<int>(N, 1), l_w = vector<int>(N, INF);
vector<int> ord(M); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) { return tie(W[i], i) < tie(W[j], j); });
vector<int> d(N);
for(int i : ord) {
int u = find(U[i], W[i]), v = find(V[i], W[i]);
++d[U[i]], ++d[V[i]];
if(u == v) {
l_w[u] = min(W[i], l_w[u]);
continue;
}
if(sz[v] < sz[u])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
p_w[u] = W[i];
if(l_w[v] <= W[i])
continue;
else if(l_w[u] <= W[i])
l_w[v] = W[i];
else if(d[U[i]] > 2 || d[V[i]] > 2)
l_w[v] = W[i];
}
}
int getMinimumFuelCapacity(int x, int y) {
auto check = [&](int w) {
int u = find(x, w), v = find(y, w);
return u == v && l_w[u] <= w;
};
if(!check(INF - 1))
return -1;
int w{0};
for(int t{INF >> 1}; t > 0; t >>= 1)
if(!check(w + t))
w += t;
return w + 1;
}
