//this is just a chatgpt try, is not my code
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9+7;
int n, m;
int LOGG; // computed from n
// adjacency by arrays
struct Edge { int to, w, next; };
vector<Edge> edges;
vector<int> head; // head[u] index of first edge, -1 none
int edge_cnt;
// up and mx stored flat: up[a*LOGG + i]
vector<int> up_flat;
vector<int> mx_flat;
inline int UP(int a, int i){ return up_flat[a * LOGG + i]; }
inline void SET_UP(int a, int i, int v){ up_flat[a * LOGG + i] = v; }
inline int MX(int a, int i){ return mx_flat[a * LOGG + i]; }
inline void SET_MX(int a, int i, int v){ mx_flat[a * LOGG + i] = v; }
vector<int> dep;
vector<int> dp;
void add_edge(int u, int v, int w){
edges[edge_cnt] = {v, w, head[u]};
head[u] = edge_cnt++;
}
void dfs(int u, int p, int d){
dep[u] = d;
for(int ei = head[u]; ei != -1; ei = edges[ei].next){
int v = edges[ei].to, c = edges[ei].w;
if(v == p) continue;
SET_UP(v, 0, u);
SET_MX(v, 0, c);
dfs(v, u, d+1);
}
}
void dfs2(int u, int p){
for(int ei = head[u]; ei != -1; ei = edges[ei].next){
int v = edges[ei].to, c = edges[ei].w;
if(v == p) continue;
dfs2(v, u);
dp[u] = min(dp[u], max(dp[v], c));
}
}
void dfs3(int u, int p){
for(int ei = head[u]; ei != -1; ei = edges[ei].next){
int v = edges[ei].to, c = edges[ei].w;
if(v == p) continue;
dp[u] = min(dp[u], max(dp[v], c));
dfs3(v, u);
}
}
// jump a up by d, also compute max weight along jump if needed
int jump_node(int a, int d){
for(int i = 0; d > 0; ++i){
if(d & 1) a = UP(a, i);
d >>= 1;
}
return a;
}
// return pair{node after jumping b up by k, maximum weight on that jump}
pair<int,int> jump_with_max(int a, int k){
int best = 0;
for(int i = 0; k; ++i){
if(k & 1){
best = max(best, MX(a, i));
a = UP(a, i);
}
k >>= 1;
}
return {a, best};
}
// LCA-like: return maximum edge weight along path between a and b
int path_max_between(int a, int b){
if(a == b) return 0;
int ans = 0;
if(dep[a] < dep[b]) swap(a,b); // ensure a deeper
int diff = dep[a] - dep[b];
// lift a up
for(int i = 0; i < LOGG; ++i){
if(diff & (1<<i)){
ans = max(ans, MX(a, i));
a = UP(a, i);
}
}
if(a == b) return ans;
for(int i = LOGG-1; i >= 0; --i){
if(UP(a,i) != UP(b,i)){
ans = max(ans, MX(a,i));
ans = max(ans, MX(b,i));
a = UP(a,i);
b = UP(b,i);
}
}
// now a and b are children of LCA
ans = max(ans, MX(a,0));
ans = max(ans, MX(b,0));
return ans;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
// compute LOGG precisely
LOGG = 1;
while((1<<LOGG) <= n) ++LOGG;
LOGG += 1; // a bit of margin
// allocate adjacency arrays
head.assign(n, -1);
edges.resize(2 * m);
edge_cnt = 0;
for(int i = 0; i < m; ++i){
int u = U[i], v = V[i], w = W[i];
add_edge(u, v, w);
add_edge(v, u, w);
}
// allocate up/mx flat arrays
up_flat.assign(n * LOGG, 0);
mx_flat.assign(n * LOGG, 0);
dep.assign(n, 0);
dp.assign(n, INF);
// initialize root 0
SET_UP(0, 0, 0);
SET_MX(0, 0, 0);
dfs(0, 0, 0);
// build binary lifting tables
for(int j = 1; j < LOGG; ++j){
for(int v = 0; v < n; ++v){
int mid = UP(v, j-1);
SET_UP(v, j, UP(mid, j-1));
SET_MX(v, j, max(MX(v, j-1), MX(mid, j-1)));
}
}
// compute dp initial (third smallest incident edge weight)
for(int u = 0; u < n; ++u){
int best1 = INF, best2 = INF, best3 = INF;
for(int ei = head[u]; ei != -1; ei = edges[ei].next){
int c = edges[ei].w;
if(c < best1){
best3 = best2;
best2 = best1;
best1 = c;
} else if(c < best2){
best3 = best2;
best2 = c;
} else if(c < best3){
best3 = c;
}
}
dp[u] = best3;
}
dfs2(0, 0);
dfs3(0, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
int pathMax = path_max_between(X, Y);
if(dp[X] == INF) return -1;
return max(pathMax, dp[X]);
}
