#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
const int N = 100005;
vec<pair<int, int>> hist[N];
vec<int> okt(N, -1);
const int INF = 1e9+5;
struct Comp {
pair<int, int> eps;
vec<int> vs;
};
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vec<Comp> comps(N);
for(int i = 0; i<N; i++) {
comps[i] = {{i, i}, {i}};
hist[i] = {{i, 0}};
}
set<pair<int, pair<int, int>>> edges;
for(int i = 0; i<M; i++) {
edges.insert({W[i], {U[i], V[i]}});
}
vec<int> ci(N);
iota(ci.begin(), ci.end(), 0);
auto upd = [&](int i, int w) {
if(okt[i] != -1) return;
okt[i] = w;
};
for(auto [weight, eps] : edges) {
auto [u, v] = eps;
if(ci[u] == ci[v]) {
upd(ci[u], weight);
continue;
}
if(comps[ci[u]].vs.size() < comps[ci[v]].vs.size()) swap(u, v);
if(u == comps[ci[u]].eps.second) swap(comps[ci[u]].eps.first, comps[ci[u]].eps.second);
if(v == comps[ci[v]].eps.second) swap(comps[ci[v]].eps.first, comps[ci[v]].eps.second);
if(okt[ci[v]] == -1 && u == comps[ci[u]].eps.first && v == comps[ci[v]].eps.first) {
comps[ci[u]].eps = {comps[ci[u]].eps.second, comps[ci[v]].eps.second};
}
else {
upd(ci[u], weight);
}
for(int w : comps[ci[v]].vs) {
ci[w] = ci[u];
comps[ci[u]].vs.push_back(w);
hist[w].push_back({ci[u], weight});
}
}
for(int i = 0; i<N; i++) {
hist[i].push_back({-1, INF});
}
}
int getMinimumFuelCapacity(int X, int Y) {
int i = 0;
int j = 0;
//cerr << okt[1] << '\n';
while(i<hist[X].size() && j < hist[Y].size()) {
if(hist[X][i].first == hist[Y][j].first && okt[hist[X][i].first] != -1) {
return max(max(hist[X][i].second, hist[Y][j].second), okt[hist[X][i].first]);
}
if(hist[X][i+1].second < hist[Y][j+1].second) {
i++;
}
else {
j++;
}
}
return -1;
}
