#include <bits/stdc++.h>
#include "swap.h"
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef pair<int, int> ii;
const int maxN = 100000;
const int maxM = 200000;
bool vst[maxN];
vector <ii> adj[maxN];
vector <int> adjEdge[maxN];
int nEdge = 0;
void buildEdge(int u, int w){
for(int v : adjEdge[u])
if (!vst[v]){
adj[u].push_back(mp(v, w));
adj[v].push_back(mp(u, w));
vst[v] = 1;
nEdge++;
buildEdge(v, w);
}
}
struct DSU{
int rnk[maxN], root[maxN], deg[maxN];
int cnt[maxN][4];
bool ok[maxN];
void reset(int n){
for(int i = 0; i < n; i++){
root[i] = i;
deg[i] = rnk[i] = 0;
cnt[i][0] = 1;
cnt[i][1] = cnt[i][2] = cnt[i][3] = 0;
ok[i] = 0;
}
}
int getRoot(int u){
if (u == root[u])
return u;
root[u] = getRoot(root[u]);
return root[u];
}
void updateDeg(int u){
int ru = getRoot(u);
cnt[ru][deg[u]]--;
deg[u]++;
cnt[ru][deg[u]]++;
}
bool check(int u){
u = getRoot(u);
if (cnt[u][3] > 0 || cnt[u][0] + cnt[u][1] == 0)
return 1;
return 0;
}
void addEdge(int u, int v, int w){
if (deg[u] < 3)
updateDeg(u);
if (deg[v] < 3)
updateDeg(v);
u = getRoot(u);
v = getRoot(v);
if (u != v){
if (rnk[u] > rnk[v])
swap(u, v);
if (rnk[u] == rnk[v])
rnk[u]++;
root[v] = u;
adjEdge[u].push_back(v);
for(int i = 0; i < 4; i++)
cnt[u][i] += cnt[v][i];
ok[u] = ok[u] || ok[v];
}
ok[u] = ok[u] || check(u);
if (ok[u])
buildEdge(u, w);
}
} G;
int dist[maxN][17], par[maxN][17], h[maxN];
void dfs(int u, int p){
for(int i = 1; i <= 16; i++){
par[u][i] = par[par[u][i - 1]][i - 1];
dist[u][i] = max(dist[u][i - 1], dist[par[u][i - 1]][i - 1]);
}
for(ii e : adj[u])
if (e.X != p){
par[e.X][0] = u;
dist[e.X][0] = e.Y;
h[e.X] = h[u] + 1;
dfs(e.X, u);
}
}
struct edge{
int u, v, w;
};
int n, m;
edge edges[maxM];
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
for(int i = 0; i < m; i++){
edges[i].u = U[i];
edges[i].v = V[i];
edges[i].w = W[i];
}
sort(edges, edges + m, [](edge &a, edge & b){
return a.w < b.w;
});
G.reset(n);
for(int i = 0; i < m; i++)
G.addEdge(edges[i].u, edges[i].v, edges[i].w);
dfs(0, -1);
}
int getDist(int u, int v){
int res = 0;
if (h[u] > h[v])
swap(u, v);
for(int i = 16; i >= 0; i--)
if (h[u] <= h[v] - (1 << i)){
res = max(res, dist[v][i]);
v = par[v][i];
}
if (v == u)
return res;
for(int i = 16; i >= 0; i--)
if (par[u][i] != par[v][i]){
res = max(res, dist[u][i]);
res = max(res, dist[v][i]);
u = par[u][i];
v = par[v][i];
}
res = max(res, dist[u][0]);
res = max(res, dist[v][0]);
return res;
}
int getMinimumFuelCapacity(int X, int Y) {
if (nEdge == 0)
return -1;
return getDist(X, Y);
}
