#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i>=(k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9 + 7;
const ll INFF = (ll)1e18;
struct dsu{
vector<int> p;
dsu(int n){
p.resize(n, -1);
}
int find(int x){
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool same_set(int u, int v){
return find(u) == find(v);
}
bool join(int u, int v){
u = find(u);
v = find(v);
if(u == v)
return false;
if(-p[u] < -p[v])
swap(u, v);
p[u] += p[v]; p[v] = u;
return true;
}
};
// mstpath + dalsia cesta z X do Y bez mstpath edges
// mstpath + neico s deg 3
int n, m;
vector<bool> on_path;
vector<vector<array<int, 2>>> g; // mst;
vector<vector<int>> g_id;
vector<vector<array<int, 2>>> initg;
bool fn = false;
void dfs(int v, int p, int dest, int ep){
if(ep != -1 && !fn)
on_path[ep] = true;
if(v == dest){
fn = true;
return;
}
REP(i, g[v].size()){
if(fn) return;
if(g[v][i][0] == p)
continue;
dfs(g[v][i][0], v, dest, g_id[v][i]);
}
if(fn) return;
if(ep != -1)
on_path[ep] = false;
}
vector<array<int, 3>> edges;
vector<int> dist;
void get_dist(int v, int p, int w){
dist[v] = w;
for(auto x : g[v]){
if(x[0] == p)
continue;
get_dist(x[0], v, max(w, x[1]));
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
g.resize(n); initg.resize(n);
g_id.resize(n);
dist.resize(n);
REP(i, m){
initg[U[i]].pb({V[i], W[i]});
initg[V[i]].pb({U[i], W[i]});
edges.pb({W[i], U[i], V[i]});
}
sort(edges.begin(), edges.end());
dsu d(n);
int id = 0;
for(auto e : edges){
if(d.same_set(e[1], e[2]))
continue;
g[e[1]].pb({e[2], e[0]});
g[e[2]].pb({e[1], e[0]});
g_id[e[1]].pb(id);
g_id[e[2]].pb(id);
d.join(e[1], e[2]);
id++;
}
auto cmp = [&](array<int, 2> f, array<int, 2> s){
return f[1] < s[1];
};
REP(i, n){
sort(initg[i].begin(), initg[i].end(), cmp);
}
}
int getMinimumFuelCapacity(int X, int Y) {
vector<int> distf, dists;
get_dist(X, -1, -INF);
distf = dist;
get_dist(Y, -1, -INF);
dists = dist;
fn = false;
on_path = vector<bool>(m, false);
dfs(X, -1, Y, -1);
int ans = INF;
int id = 0;
dsu d(n);
if(m != n - 1){
for(auto e : edges){
//cout << X << " " << Y << " " << id << " " << on_path[id] << "\n";
if(on_path[id]){
id++;
continue;
}
d.join(e[1], e[2]);
if(d.same_set(X, Y)){
ans = min(ans, max(e[0], distf[Y]));
break;
}
id++;
}
}
REP(i, n){
if(initg[i].size() > 2){
ans = min(ans, max({distf[Y], distf[i], dists[i], initg[i][2][1]}));
}
}
if(ans == INF){
return -1;
}
return ans;
return 0;
}
