#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 200005;
const int inf = 1e6;
int n,k,ans;
int cur, h[maxn], sz[maxn], st[maxn], ft[maxn], p[maxn];
long long sum[maxn];
vector<int> go[maxn];
vector<pii> edge[maxn];
map<long long,int> s;
void dfs(int u,int last) {
st[u] = ++cur; p[cur] = u;
sz[u] = 1; h[u] = h[last]+1;
for(auto t : edge[u]) {
int v = t.X, val = t.Y;
if(v!=last) {
sum[v] = sum[u] + val;
dfs(v,u);
sz[u] += sz[v];
}
}
ft[u] = cur;
// printf("%d : [%d, %d] h = %d sz = %d sum = %lld\n",u,st[u],ft[u],h[u],sz[u],sum[u]);
}
void add(long long x,int val) {
if(s.find(x)==s.end()) s[x] = val;
else s[x] = min(s[x],val);
}
int get(long long x) {
if(s.find(x)==s.end()) return inf;
return s[x];
}
void solve(int u,int last,int keep) {
int mx = 0, big = -1;
for(auto v : go[u]) if(v!=last && sz[v]>mx) mx = sz[v], big = v;
for(auto v : go[u]) if(v!=last && v!=big) solve(v,u,0);
if(big!=-1) solve(big,u,1);
//solve
// printf("solve %d\n",u);
add(sum[u],h[u]);
ans = min(ans,get(k+sum[u])-h[u]);
for(auto v : go[u]) {
if(v!=last && v!=big) {
for(int i=st[v];i<=ft[v];i++) {
// printf("\ttry %d : (%lld) : want %lld\n",p[i],sum[p[i]],k-sum[p[i]]+2*sum[u]);
ans = min(ans,get(k-sum[p[i]]+2*sum[u])+h[p[i]]-2*h[u]);
}
for(int i=st[v];i<=ft[v];i++) add(sum[p[i]],h[p[i]]);
}
}
//delete
if(!keep) s.clear();
}
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 x = H[i][0]+1, y = H[i][1]+1, val = L[i];
edge[x].push_back({y,val}); edge[y].push_back({x,val});
go[x].push_back(y); go[y].push_back(x);
}
dfs(1,0);
ans = inf;
solve(1,0,0);
if(ans>n) return -1;
return ans;
}
