#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 2e5 + 5;
const int LOG = __lg(MaxN);
#define all(x) (x).begin(), (x).end()
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }
const int Inf = 1e9 + 1e8;
int id[MaxN];
vector<int> w;
namespace Dsu {
int f[MaxN];
int size[MaxN];
int cache_time = -1;
int time_changed[MaxN];
int cycle_time[MaxN];
int deg[MaxN];
vector<pair<int, int>> max_deg[MaxN];
void init(int n) {
cache_time = -1;
for (int i = 0; i < n; ++i) {
time_changed[i] = -1;
cycle_time[i] = Inf;
size[i] = 1;
f[i] = i;
deg[i] = 0;
max_deg[i].push_back({-1, 0});
}
}
int fset(int u, int time) {
if (u == f[u] || time_changed[u] > time)
return u;
return fset(f[u], time);
}
void uset(int u, int v, int time = ++cache_time) {
int U = u, V = v;
u = fset(u, time);
v = fset(v, time);
if (u != v) {
if (size[u] > size[v])
swap(u, v);
f[u] = v;
size[v] += size[u];
time_changed[u] = time;
minimize(cycle_time[v], cycle_time[u]);
} else {
minimize(cycle_time[u], time);
}
++deg[U]; ++deg[V];
int best = max({deg[U], deg[V], max_deg[v].back().second});
if (best > max_deg[v].back().second)
max_deg[v].push_back({time, best});
}
int cycled(int u, int time) {
return cycle_time[u] <= time;
}
}
using namespace Dsu;
void init(int N, int M, std::vector<int> u, std::vector<int> v, std::vector<int> W) {
w = W;
iota(id, id + M, 0);
sort(id, id + M, [&](int i, int j) {
return w[i] < w[j];
});
init(N);
for (int i = 0; i < M; ++i) {
int j = id[i];
uset(u[j], v[j]);
}
}
int getMinimumFuelCapacity(int u, int v) {
int l = 0, r = w.size() - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int x = fset(u, mid);
int y = fset(v, mid);
if (x == y) {
auto it = upper_bound(all(max_deg[x]), make_pair(mid, 0));
if (cycled(x, mid) || (it -> second) > 2) {
ans = w[id[mid]];
r = mid - 1;
} else {
l = mid + 1;
}
} else {
l = mid + 1;
}
}
return ans;
}
