// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 20;
constexpr int MOD = 1e9+7;
struct Node {
bool isl;
array<int,2> e;
int p;
int sz;
int ver;
Node() {}
};
struct DSU {
vector<Node> dt;
int cnt = 0;
void reset(int s) {
dt.resize(s + 3);
}
void make_set(int x) {
dt[x].p = x;
dt[x].isl = 1;
dt[x].e = {x, x};
dt[x].sz = 1;
dt[x].ver = cnt++;
}
int find_set(int x) {
return (x == dt[x].p) ? x : dt[x].p = find_set(dt[x].p);
}
int union_set(int x, int y) { // 0 nothing, 1 turned into non line, 2 merged as line, 3 merged and non line
int a = x, b = y;
x = find_set(x); y = find_set(y);
dt[x].ver = dt[y].ver = cnt++;
if(x == y) {
dt[x].isl = 0;
return 1;
}
if(dt[x].sz < dt[y].sz) {
swap(a, b);
swap(x, y);
}
dt[x].sz += dt[y].sz;
dt[y].p = x;
if(dt[x].isl && dt[y].isl && (dt[x].e[0] == a || dt[x].e[1] == a) && (dt[y].e[0] == b || dt[y].e[1] == b)) {
int en = dt[y].e[0];
if(dt[y].e[0] == b) en = dt[y].e[1];
if(dt[x].e[0] == a) dt[x].e[0] = en;
else dt[x].e[1] = en;
return 2;
}
else {
dt[x].isl = 0;
return 3;
}
}
};
int n,m,s;
vector<array<int,3> > edges;
vector<vector<int> > anc;
vector<int> cst;
vector<bool> stat;
void prec() {
for(int k = 1; k < LGN; k++) {
for(int i = 0; i < s; i++) {
anc[i][k] = anc[anc[i][k - 1]][k - 1];
}
}
}
bool check(int val, int x, int y) {
for(int k = LGN - 1; k >= 0; k--) {
if(cst[anc[x][k]] <= val) {
x = anc[x][k];
}
if(cst[anc[y][k]] <= val) {
y = anc[y][k];
}
}
// cout << x << " " << y << " xy" << endl;
if(x != y) return 0;
if(!stat[x]) return 0;
return 1;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M; s = N + M;
edges.resize(M);
REP(i,M) {
edges[i] = {W[i], U[i], V[i]};
}
sort(all(edges));
anc.assign(s, vector<int>(LGN, s - 1));
cst.assign(s, 0);
stat.assign(s, 0);
DSU ds;
ds.reset(n);
REP(i,n) {
stat[i] = 0;
ds.make_set(i);
}
for(auto &c : edges) {
anc[ds.dt[ds.find_set(c[1])].ver][0] = ds.cnt;
anc[ds.dt[ds.find_set(c[2])].ver][0] = ds.cnt;
int ret = ds.union_set(c[1], c[2]);
if(ret & 1) {
stat[ds.cnt - 1] = 1;
}
cst[ds.cnt - 1] = c[0];
}
// for(int i = 0; i < s ; i++) {
// cout << "i:" << i << " " << stat[i] << " " << cst[i] << "par: " << anc[i][0] << "\n";
// }
prec();
}
int getMinimumFuelCapacity(int X, int Y) {
int tl = 0, tr = m - 1;
while(tl < tr) {
int tm = (tl + tr) >> 1;
if(check(edges[tm][0], X, Y)) {
tr = tm;
}
else {
tl = tm + 1;
}
}
if(!check(edges[tl][0], X, Y)) {
tl++;
}
// cout << check(4, X, Y) << " val4" << endl;
if(tl >= m) return -1;
return edges[tl][0];
}
