#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
const int MAXM = 2e5;
const int inf = 1e9;
class edge {
public:
int u, v, w;
edge(int u, int v, int w) : u(u), v(v), w(w) {}
edge() {}
};
bool operator<(edge &a, edge &b) {
return (a.w == b.w) ? (a.u == b.u) ? (a.v < b.v) : (a.u < b.u) : (a.w < b.w);
}
edge edges[MAXM];
vector<pii> par[MAXN]; // time, val
vector<int> in_set[MAXN];
map<int, int> compress;
int comp_inv[MAXM];
int nice_pos[MAXN];
pii epoints[MAXN];
int t;
void merge(int a, int b) {
int an = par[a].back().second;
int bn = par[b].back().second;
if (an == bn) {
nice_pos[an] = min(nice_pos[an], t);
return;
}
if (in_set[an].size() < in_set[bn].size()) {
swap(a, b);
swap(an, bn);
}
for (int v: in_set[bn]) {
in_set[an].push_back(v);
par[v].push_back(pii(t, an));
}
if ((a == epoints[an].first || a == epoints[an].second) &&
(b == epoints[bn].first || b == epoints[bn].second)) {
epoints[an] = pii(epoints[an].first+epoints[an].second-a, epoints[bn].first+epoints[bn].second-b);
}
else {
nice_pos[an] = min(nice_pos[an], t);
}
nice_pos[an] = min(nice_pos[an], max(t, nice_pos[bn]));
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < m; i++) edges[i] = edge(U[i], V[i], W[i]);
sort(W.begin(), W.end());
for (int w: W) {
if (compress.find(w) == compress.end()) {
compress[w] = compress.size();
comp_inv[compress.size()-1] = w;
}
}
for (int i = 0; i < m; i++) edges[i].w = compress[edges[i].w];
sort(edges, edges+m);
for (int i = 0; i < n; i++) {
par[i].push_back(pii(-1, i));
in_set[i].push_back(i);
nice_pos[i] = inf;
epoints[i] = pii(i, i);
}
int j = 0;
for (int i = 0; i < compress.size(); i++) {
t = i;
while (j < m && edges[j].w == i) {
merge(edges[j].u, edges[j].v);
j++;
}
}
}
int get_par(int x, int cur) {
int mn = 0;
int mx = par[x].size();
while (mx > mn+1) {
int cval = (mn+mx)/2;
if (par[x][cval].first <= cur) mn = cval;
else mx = cval;
}
return par[x][mn].second;
}
int getMinimumFuelCapacity(int x, int y) {
int mn = -1;
int mx = compress.size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
int p1 = get_par(x, cur);
int p2 = get_par(y, cur);
if (p1 == p2 && nice_pos[p1] <= cur) mx = cur;
else mn = cur;
}
if (mx == compress.size()) {
return -1;
}
return comp_inv[mx];
}
