#include "swap.h"
#include <vector>
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Tran The Bao - ghostwriter
Training for VOI23 gold medal
----------------------------------------------------------------
GOAT
----------------------------------------------------------------
*/
struct Edge {
int u, v, w;
Edge() {}
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
bool operator <(const Edge &b) { return w < b.w; }
};
struct Status {
int time, cnt[4];
Status() { time = 0; memset(cnt, 0, sizeof cnt); }
};
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
int edgenum, p[MAXN], w1[MAXN], cpos[MAXN], d[MAXN];
Status csta[MAXN];
Edge e[MAXM];
vi vt[MAXN];
vpi pos[MAXN];
vector<Status> sta[MAXN];
void join(int u, int v, int w) {
int un = cpos[u], vn = cpos[v];
if (sz(vt[un]) < sz(vt[vn])) {
swap(u, v);
swap(un, vn);
}
if (un != vn) {
EACH(i, vt[vn]) {
vt[un].pb(i);
pos[i].pb({w, un});
cpos[i] = un;
}
FRN(i, 4) csta[un].cnt[i] += csta[vn].cnt[i];
}
--csta[un].cnt[min(d[u], 3)];
--csta[un].cnt[min(d[v], 3)];
++d[u];
++d[v];
++csta[un].cnt[min(d[u], 3)];
++csta[un].cnt[min(d[v], 3)];
sta[un].pb(Status());
sta[un].bk().time = w;
FRN(i, 4) sta[un].bk().cnt[i] = csta[un].cnt[i];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
edgenum = M;
FRN(i, M) w1[i] = W[i];
sort(w1, w1 + M);
w1[M] = -1;
FRN(i, M) {
W[i] = lb(w1, w1 + M, W[i]) - w1;
e[i] = Edge(U[i], V[i], W[i]);
}
sort(e, e + M);
FRN(i, N) {
vt[i].pb(i);
pos[i].pb({0, i});
cpos[i] = i;
csta[i].cnt[0] = 1;
}
FRN(i, M) {
int u = e[i].u, v = e[i].v, w = e[i].w;
join(u, v, w);
}
}
int getp(int u, int time) {
int l = 0, r = sz(pos[u]) - 1, ans = -1;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (pos[u][mid].st <= time) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return pos[u][ans].nd;
}
Status gets(int u, int time) {
int l = 0, r = sz(sta[u]) - 1, ans = -1;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (sta[u][mid].time <= time) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return sta[u][ans];
}
bool check(int X, int Y, int time) {
int px = getp(X, time), py = getp(Y, time);
if (px != py) return 0;
Status cur = gets(px, time);
if (cur.cnt[3]) return 1;
int total = 0; FRN(i, 4) total += cur.cnt[i];
if (cur.cnt[2] == total - 2) return 0;
return 1;
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = edgenum - 1, ans = edgenum;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (check(X, Y, mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return w1[ans];
}
/*
3 2
0 1 5
0 2 5
1
1 2
*/
