#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll int
ll n,m,u,v,w,child[200005],ans,d;
vector<pair<ll,ll>>a[200005];
bool del[200005];
map<ll,ll>mp;
vector<pair<ll,ll>>vc;
void dfsmake(ll x,ll pa)
{
child[x]=1;
for(pair<ll,ll> it:a[x])
if(del[it.first]==0&&it.first!=pa)
{
dfsmake(it.first,x);
child[x]+=child[it.first];
}
}
ll getcentroid(ll x,ll pa,ll n)
{
for(pair<ll,ll> it:a[x])
if(it.first!=pa&&del[it.first]==0&&child[it.first]>n/2)
return getcentroid(it.first,x,n);
return x;
}
void dfsgetans(ll x,ll pa,ll dist)
{
// cout<<d<<" "<<m-d<<'\n';
if(m-d<0)
return;
vc.push_back({d,dist});
// cout<<m-d<<" "<<d<<" "<<mp[m-d]<<' '<<dist<<'\n';
if(m-d==0)
ans=min(ans,dist);
else if(mp[m-d]!=0)
ans=min(ans,dist+mp[m-d]);
for(pair<ll,ll> it:a[x])
if(it.first!=pa&&del[it.first]==0)
{
d+=it.second;
dfsgetans(it.first,x,dist+1);
d-=it.second;
}
}
void dfscentroid(ll x,ll pa)
{
dfsmake(x,0);
ll u=getcentroid(x,0,child[x]);
for(pair<ll,ll> it:a[u])
if(del[it.first]==0)
{
d=it.second;
dfsgetans(it.first,u,1);
for(pair<ll,ll>it:vc)
{
if(mp[it.first]==0)
mp[it.first]=it.second;
else
mp[it.first]=min(mp[it.first],it.second);
}
vc.clear();
}
mp.clear();
// cout<<u<<" "<<ans<<'\n';
del[u]=1;
for(pair<ll,ll> it:a[u])
if(del[it.first]==0)
dfscentroid(it.first,u);
}
int best_path(int N,int M,int H[][2],int L[])
{
m=M;
n=N;
for(int i=0;i<=n-2;i++)
{
u=H[i][0]+1;
v=H[i][1]+1;
w=L[i];
// cout<<u<<" "<<v<<" "<<w<<'\n';
a[u].push_back({v,w});
a[v].push_back({u,w});
}
ans=1e9;
dfscentroid(n,0);
if(ans!=1e9)
return ans;
return -1;
}
//int main()
//{
// int HH[10005][2];
// HH[0][0]=0;
// HH[0][1]=1;
// HH[1][0]=1;
// HH[1][1]=2;
// HH[2][0]=1;
// HH[2][1]=3;
//
// int LH[10005];
// LH[0]=1;
// LH[1]=2;
// LH[2]=4;
// cout<<best_path(4,3,HH,LH);
//}
//
