#include "swap.h" //"grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define D(x) cerr << #x << ": " << x << endl;
int n, m;
vi weights;
vector<vector<pi>> w_to_edges;
struct History {
int curr = -1;
map<int, int> time_to_val;
History() {
time_to_val = {};
update(0, 0);
}
History(int val) {
time_to_val = {};
update(0, val);
}
void update(int time, int val) {
if (val == curr) return;
time_to_val[time] = val;
curr = val;
}
int at_time(int time) {
auto iter = time_to_val.upper_bound(time);
iter--;
return (*iter).second;
}
};
const int MAX_N = 100001;
int sz[MAX_N];
History parent[MAX_N], flag[MAX_N], neicount[MAX_N];
int root(int a) {
if (parent[a].curr != a) return root(parent[a].curr);
else return a;
}
int root_at(int tm, int a) {
int par = parent[a].at_time(tm);
if (par != a) return root_at(tm, par);
else return a;
}
void join(int tm, int u, int v) {
int a = root(u);
int b = root(v);
neicount[u].update(tm, neicount[u].curr+1);
neicount[v].update(tm, neicount[v].curr+1);
if (neicount[u].curr == 3 || neicount[v].curr == 3) flag[a].update(tm, 1);
if (a == b) {
flag[a].update(tm, 1); // cycle
return;
}
if (sz[a] < sz[b]) swap(a,b);
parent[b].update(tm, a);
sz[a] += sz[b];
if (flag[b].curr) flag[a].update(tm, 1);
}
bool were_good(int tm, int u, int v) {
bool yay = false; //neicount[u].at_time(tm)>=2 || neicount[v].at_time(tm)>=2;
u = root_at(tm, u); v = root_at(tm, v);
yay = yay || flag[u].at_time(tm);
return u == v && yay;
}
void go_insert() {
REP(tm, weights.size()) {
trav(e, w_to_edges[tm]) {
join(tm+1, e.first, e.second);
}
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
vector<pi> wp(m);
REP(i,m) wp[i] = {W[i], i};
sort(all(wp));
int ind = -1, prev = -1;
REP(i, m) {
if (wp[i].first != prev) {
prev = wp[i].first; ind++;
weights.push_back(prev);
w_to_edges.push_back(vector<pi>());
}
int j = wp[i].second;
w_to_edges[ind].push_back({U[j], V[j]});
}
REP(i,n) parent[i] = History(i);
REP(i,n) sz[i] = 1;
go_insert();
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = weights.size()+1;
while (l < r) {
int mid = (l+r)/2;
if (were_good(mid, X, Y)) {
r = mid;
} else {
l = mid+1;
}
}
assert(l==r);
assert(l!=0);
if (l > weights.size()) return -1;
else return weights[l-1];
}
