// You can't change other people; you can only change yourself.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "swap.h"
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;
// Data types
using i8 = __int128;
using ll = long long;
using si = short int;
using ld = long double;
// Pairs
using pi8 = pair<i8, i8>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using psi = pair<si, si>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
// Constants
const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
struct OnlineDSU {
int n;
vector<vector<pii>> par, sz, degree, maxdegree, edgecount;
OnlineDSU(int _n) {
n = _n;
for (int i = 0; i < n; i++) {
par.push_back({{0, i}});
}
sz.assign(n, {{0, 1}});
degree.assign(n, {{0, 0}});
maxdegree.assign(n, {{0, 0}});
edgecount.assign(n, {{0, 0}});
}
void insert(vector<pii> &v, int val, int t) {
if (v.back().se == val) {return;}
if (v.back().fi == t) {
v.back().se = val;
} else {
v.push_back({t, val});
}
}
int query(vector<pii> &v, int t) {
pii search = {t+1, -iINF};
auto it = upper_bound(v.begin(), v.end(), search);
it--;
return it->second;
}
int parent_latest(int x) {return par[x].back().se;}
int size_latest(int x) {return sz[x].back().se;}
int degree_latest(int x) {return degree[x].back().se;}
int maxdegree_latest(int x) {return maxdegree[x].back().se;}
int edgecount_latest(int x) {return edgecount[x].back().se;}
int get_degree(int x, int t) {return query(degree[x], t);}
int get_maxdegree(int x, int t) {return query(maxdegree[x], t);}
int get_edgecount(int x, int t) {return query(edgecount[x], t);}
int get_size(int x, int t) {return query(sz[x], t);}
int rep_latest(int x, int t) {
if (x == parent_latest(x)) {return x;}
insert(par[x], rep_latest(parent_latest(x), t), t);
return parent_latest(x);
}
int rep(int x, int t) {
int p = query(par[x], t);
if (x == p) {return x;}
return rep(p, t);
}
void join_latest(int u, int v, int t) {
insert(degree[u], degree_latest(u)+1, t);
insert(degree[v], degree_latest(v)+1, t);
int x = rep_latest(u, t), y = rep_latest(v, t);
if (x != y) {
if (size_latest(x) < size_latest(y)) {swap(x, y);}
insert(par[y], x, t);
insert(sz[x], size_latest(x) + size_latest(y), t);
int mx = maxdegree_latest(x), my = maxdegree_latest(y);
insert(maxdegree[x], max(max(mx, my), max(degree_latest(u), degree_latest(v))), t);
int ex = edgecount_latest(x), ey = edgecount_latest(y);
insert(edgecount[x], ex+ey+1, t);
} else {
insert(maxdegree[x], max(maxdegree_latest(x), max(degree_latest(u), degree_latest(v))), t);
int e = edgecount_latest(x);
insert(edgecount[x], e+1, t);
}
}
bool check(int u, int v, int t) {
int x = rep(u, t), y = rep(v, t);
return (x == y);
}
};
void print(vector<vector<pii>> &v) {
for (int i = 0; i < v.size(); i++) {
cout << i << ": ";
for (auto j : v[i]) {
cout << "{" << j.fi << ", " << j.se << "} ";
}
cout << '\n';
}
cout << '\n';
}
using Edge = pair<int, pii>;
OnlineDSU *D;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
vector<Edge> E;
for (int i = 0; i < M; i++) {
E.push_back({W[i], {U[i], V[i]}});
}
sort(E.begin(), E.end());
D = new OnlineDSU(N);
for (auto x : E) {
D->join_latest(x.se.fi, x.se.se, x.fi);
//printf("%d: %d %d\n", x.fi, x.se.fi, x.se.se);
}
/*
cout << "par\n";
print(D->par);
cout << "sz\n";
print(D->sz);
cout << "degree\n";
print(D->degree);
cout << "maxdegree\n";
print(D->maxdegree);
cout << "edgecount\n";
print(D->edgecount);
*/
}
const int MAX = 1e9;
int getMinimumFuelCapacity(int X, int Y) {
int L = 1, R = MAX, ans = -1;
while (L <= R) {
int M = (L + R) >> 1;
bool pos = 1;
if (!D->check(X, Y, M)) {
pos = 0;
} else {
int R = D->rep(X, M);
if (D->get_maxdegree(R, M) > 2 || (D->get_size(R, M) == D->get_edgecount(R, M))) {
pos = 1;
} else {
pos = 0;
}
}
if (pos) {
R = M - 1;
ans = M;
} else {
L = M + 1;
}
}
return ans;
}
//int main() {}
