#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=200001;
vector<pair<int, int>>adj[maxn];
vector<int>dth(maxn), dst(maxn);
map<int, int>mps[maxn]; //map[dist] -> dep
int k, ans;
void check(int v, int dsta, int dtha){
int dstb=k+2*dst[v]-dsta;
if(mps[v].count(dstb)){
int dthb=mps[v][dstb];
ans=min(ans, dthb+dtha-2*dth[v]);
if(ans==-1) cout<<"me\n";
}
}
void add(int v, int dsta, int dtha){
if(mps[v].count(dsta)) mps[v][dsta]=min(mps[v][dsta], dtha);
else mps[v][dsta]=dtha;
}
void dfs(int i, int j){
dth[i]=dth[j]+1;
int m=-1;
for(auto [k, w] : adj[i]) if(k!=j){
dst[k]=dst[i]+w;
dfs(k, i);
if(m==-1 or mps[m].size()<mps[k].size()) m=k;
}
if(m!=-1) swap(mps[m], mps[i]);
check(i, dst[i], dth[i]);
add(i, dst[i], dth[i]);
for(auto [k, w] : adj[i]){
if(k!=m or k!=j){
for(auto [dsta, dtha] : mps[k]) check(i, dsta, dtha);
for(auto [dsta, dtha] : mps[k]) add(i, dsta, dtha);
}
}
}
int best_path(int n, int K, int h[][2], int l[])
{
ans=n;
k=K;
for(int i=0; i<n-1; i++){
int u=h[i][0], v=h[i][1];
adj[u].push_back({v, l[i]});
adj[v].push_back({u, l[i]});
}
dfs(0, n);
return ans==n ? -1 : ans;
}
