#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXM = 2e5;
struct Edge
{
int u, v, w;
};
int N, M;
vector<pii> adj[MAXN+10];
Edge E[MAXM+10];
int deg[MAXN+10];
int par[MAXN+10], maxd[MAXN+10], sz[MAXN+10], ecnt[MAXN+10];
vector<pii> adj2[MAXN+10];
int T[MAXN+10];
int Find(int x)
{
if(x==par[x]) return x;
return Find(par[x]);
}
vector<int> V[MAXN+10];
void Union(int x, int y)
{
x=Find(x); y=Find(y);
if(x==y) return;
if(sz[x]>sz[y]) swap(x, y);
for(auto it : V[x]) V[y].push_back(it);
V[x].clear();
par[x]=y;
maxd[y]=max(maxd[y], maxd[x]);
sz[y]+=sz[x];
ecnt[y]+=ecnt[x];
}
int ppar[MAXN+10][30], dep[MAXN+10], spa[MAXN+10][30];
void dfs(int now, int bef, int d, int val)
{
dep[now]=d;
ppar[now][0]=bef;
spa[now][0]=val;
for(auto nxt : adj2[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now, d+1, nxt.second);
}
}
int maxdist(int u, int v)
{
int ans=0;
if(dep[u]>dep[v]) swap(u, v);
for(int i=20; i>=0; i--) if(dep[ppar[v][i]]>=dep[u])
{
ans=max(ans, spa[v][i]);
v=ppar[v][i];
}
if(u==v) return ans;
for(int i=20; i>=0; i--) if(ppar[u][i]!=ppar[v][i])
{
ans=max(ans, spa[u][i]);
ans=max(ans, spa[v][i]);
u=ppar[u][i]; v=ppar[v][i];
}
ans=max(ans, spa[u][0]);
ans=max(ans, spa[v][0]);
return ans;
}
void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W)
{
N=_N; M=_M;
for(int i=0; i<M; i++)
{
int u=_U[i]+1, v=_V[i]+1, w=_W[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
E[i+1]={u, v, w};
}
sort(E+1, E+M+1, [&](const Edge &p, const Edge &q) { return p.w<q.w; });
for(int i=1; i<=N; i++)
{
deg[i]=0;
maxd[i]=0;
par[i]=i;
sz[i]=1; ecnt[i]=0;
T[i]=1e9;
V[i].push_back(i);
}
for(int i=1; i<=M; i++)
{
int u=E[i].u, v=E[i].v, w=E[i].w;
deg[u]++; deg[v]++;
if(Find(u)!=Find(v))
{
//printf("%d %d %d\n", u, v, w);
adj2[u].push_back({v, w});
adj2[v].push_back({u, w});
Union(u, v);
}
ecnt[Find(u)]++;
maxd[Find(u)]=max(maxd[Find(u)], max(deg[u], deg[v]));
if(maxd[Find(u)]>=3 || (maxd[Find(u)]==2 && ecnt[Find(u)]==sz[Find(u)]))
{
for(auto it : V[Find(u)]) T[it]=E[i].w;
V[Find(u)].clear();
}
//if(Find(X)==Find(Y) && maxd[Find(X)]==2 && ecnt[Find(X)]==sz[Find(X)]) { ans=E[i].w; break; }
}
dfs(1, 1, 1, 0);
for(int i=1; i<=20; i++) for(int j=1; j<=N; j++)
{
ppar[j][i]=ppar[ppar[j][i-1]][i-1];
spa[j][i]=max(spa[j][i-1], spa[ppar[j][i-1]][i-1]);
}
//for(int i=1; i<=N; i++) printf("T %d : %d\n", i, T[i]);
}
int X, Y;
int getMinimumFuelCapacity(int _X, int _Y)
{
X=_X+1; Y=_Y+1;
int ans=maxdist(X, Y);
ans=max(ans, T[X]);
ans=max(ans, T[Y]);
if(ans>=1e9) ans=-1;
return ans;
}
