#include<bits/stdc++.h>
using namespace std;
#include "race.h"
// Do everything in global distance because it simplifies work
const int MX = 2e5 + 10;
int ans = 1e9, n, k, timer = 0, d[MX], tin[MX], tout[MX], st[MX], big[MX], siz[MX], edges[MX];
vector<pair<int,int>> adj[MX];
map<int,int> hold;
void dfs2(int i,int p,bool keep){
for(auto [e, w] : adj[i]){
if(e != p && e != big[i])
dfs2(e, i,false);
}
if(big[i] != -1)
dfs2(big[i], i, true);
hold[d[i]] = edges[i];
int total = k + 2*d[i];
if(hold.find(total - d[i]) != hold.end())
ans = min(ans, hold[total - d[i]] - edges[i]);
for(auto [e, w] : adj[i]){
if(e != p && e != big[i]){
for(int tim = tin[e];tim<=tout[e];tim++){
int id = st[tim];
if(hold.find(total - d[id]) != hold.end())
ans = min(ans, hold[total - d[id]] + edges[id] - 2*edges[i]);
}
for(int tim = tin[e];tim<=tout[e];tim++){
int id = st[tim];
hold[d[id]] = min(hold[d[id]], edges[id]);
}
}
}
if(!keep){
hold[d[i]] = 1e8;
for(auto [e,w] : adj[i]){
if(e != p){
for(int tim = tin[e];tim<=tout[e];tim++){
int id = st[tim];
hold[d[i]] = 1e8;
}
}
}
}
}
void dfs1(int i,int p){
int tt = -1;
big[i] = -1;
siz[i] = 1;
st[++timer] = i;
tin[i] = timer;
big[i] = -1;
for(auto [e, w] : adj[i]){
if(e == p)continue;
d[e] = d[i] + w;
edges[e] = edges[i] + 1;
hold[d[e]] = 1e8;
dfs1(e, i);
siz[i] += siz[e];
if(siz[e] > tt){
big[i] = e;
tt = siz[e];
}
}
tout[i] = timer;
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0;i<n - 1;i++){
int a = H[i][0],b = H[i][1], w = L[i];
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
d[0] = 0;
dfs1(0, -1);
dfs2(0,-1,true);
if(ans > N)
ans = -1;
return ans;
}
