#include"bits/stdc++.h"
#include "race.h"
#define overload(a,b,c,d,...) d
#define rep1(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep2(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
int best_path(int n,int k,int h[][2],int l[]){
vector<vector<pair<int,ll>>>g(n);
rep(i,n-1){
g[h[i][0]].eb(h[i][1],l[i]);
g[h[i][1]].eb(h[i][0],l[i]);
}
vector<pair<ll,int>>dist(n,{1e9,1e9});
{
queue<int>que;
que.emplace(0);
dist[0]=pair<ll,int>{0,0};
while(!que.empty()){
int v=que.front();que.pop();
for(auto [e,c]:g[v])if(dist[e].second==1e9){
dist[e].first=dist[v].first+c;
dist[e].second=dist[v].second+1;
que.push(e);
}
}
}
vector<set<pair<int,ll>>>st(n);
int ans=1e9;
auto dfs=[&](auto&&dfs,ll v,ll p=-1)->void {
st[v].emplace(dist[v]);
for(auto [u,c]:g[v])if(u!=p){
dfs(dfs,u,v);
if(st[v].size()<st[u].size())swap(st[u],st[v]);
for(auto [d1,d2]:st[u]){
//d1+d-2*dist[v].first=k
auto it=st[v].lower_bound({2*dist[v].first+k-d1,-1});
if(it!=st[v].end()&&it->first==2*dist[v].first+k-d1){
chmin(ans,it->second+d2-2*dist[v].second);
}
}
for(auto [d1,d2]:st[u])st[v].emplace(d1,d2);
st[u].clear();
}
};
dfs(dfs,0);
if(ans==1e9)ans=-1;
return ans;
}
