#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, ll>
#define F first
#define S second
const int N = 10005;
const int mod = 1e9+7;
int par[1005][20], hgh[N], tin[N], tout[N], tmr = 1;
ll dis[N];
vector<pii> a[N];
void DFS(int node){
for(int i = 1; i <= 10; i++){
par[node][i] = par[par[node][i - 1]][i - 1];
}
tin[node] = tmr;
tmr++;
for(pii i : a[node]){
if(i.F != par[node][0]){
par[i.F][0] = node;
dis[i.F] = dis[node] + i.S;
hgh[i.F] = hgh[node] + 1;
DFS(i.F);
}
}
tout[node] = tmr;
tmr++;
}
bool ispar(int a, int b){
if(tin[a] < tin[b] && tout[b] < tout[a]) return true;
return false;
}
int LCA(int a, int b){
if(ispar(a, b)) return a;
if(ispar(b, a)) return b;
if(hgh[a] < hgh[b]) swap(a, b);
for(int i = 10; i >= 0; i--){
if(par[a][i] == -1) continue;
if(!ispar(par[a][i], b)) a = par[a][i];
}
return par[a][0];
}
int best_path(int n, int k, int h[][2], int l[]){
for(int i = 0; i < n - 1; i++){
int u = h[i][0];
int v = h[i][1];
a[u].pb({v, l[i]});
a[v].pb({u, l[i]});
for(int j = 0; j < 11; j++) par[i][j] = -1;
}
for(int j = 0; j < 11; j++) par[n - 1][j] = -1;
DFS(0);
int ans = n + 5;
for(int i = 0; i <= n; i++){
for(int j = i + 1; j <= n; j++){
int anc = LCA(i, j);
ll lnt = dis[i] + dis[j] - dis[anc] - dis[anc];
if(lnt == k){
ans = min(ans, hgh[i] + hgh[j] - hgh[anc] - hgh[anc]);
}
}
}
if(ans == n + 5) return -1;
return ans;
}
