#include "swap.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=3e5+5;
const int LG=19;
int par[nx], up[nx][LG], deg[nx], sz, wei[nx], h[nx];
vector<int> adj[nx];
bool ok[nx], ck[nx][LG];
int find(int u)
{
if(!par[u]) return u;
return par[u]=find(par[u]);
}
void join(int u, int v, int w)
{
int x=u, y=v;
deg[x]++;
deg[y]++;
u=find(u);
v=find(v);
sz++;
adj[sz].emplace_back(u);
wei[sz]=w;
par[u]=sz;
if(u!=v)
{
adj[sz].emplace_back(v);
par[v]=sz;
}
ok[sz]=ok[u]|ok[v]|(u==v)|(deg[x]>2)|(deg[y]>2);
}
void dfs(int u)
{
for(int v:adj[u])
{
up[v][0]=u;
h[v]=h[u]+1;
ck[v][0]=ok[v];
for(int i = 1; i < LG; i++)
{
up[v][i]=up[up[v][i-1]][i-1];
ck[v][i]=ck[v][i-1]|ck[up[v][i-1]][i-1];
}
dfs(v);
}
}
int jump(int u, int k)
{
for(int i = 0; i < LG; i++)
if(k>>i&1) u=up[u][i];
return u;
}
int lca(int u, int v)
{
if(h[u]<h[v]) swap(u, v);
u=jump(u, h[u]-h[v]);
if(u==v) return u;
for(int i = LG-1; i >= 0; i--)
if(up[u][i]!=up[v][i])
u=up[u][i], v=up[v][i];
return up[u][0];
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W)
{
vector<pair<int, ii>> ed={};
for(int i = 0; i < m; i++)
ed.push_back({W[i], {U[i]+1, V[i]+1}});
sort(ed.begin(), ed.end());
for(int i = 1; i <= n+m; i++)
par[i]=0, deg[i]=0, adj[i].clear(), ok[i]=0;
sz=n;
for(auto it:ed)
{
int u, v;
tie(u, v)=it.se;
join(u, v, it.fi);
}
h[sz]=0;
dfs(sz);
}
int getMinimumFuelCapacity(int u, int v)
{
u++, v++;
int p=lca(u, v);
for(int i = LG-1; i >= 0; i--)
if(up[p][i] && !ck[p][i]) p=up[p][i];
if(ok[p]) return wei[p];
return -1;
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// }
