#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ertunt return
#define vodka void
set<pair<int,int>> v[200005];
vector<int> si(200005,0);
int n = 0;
int centroid(int x, int p){
for(auto [u,w] : v[x]){
if(u == p) continue;
if(si[u]*2 > n) ertunt centroid(u,x);
}
ertunt x;
}
void calc(int x, int p){
n++;
si[x] = 1;
for(auto [u,w] : v[x]){
if(u == p) continue;
calc(u,x);
si[x] += si[u];
}
}
int best_path(int n, int k, int h[][2], int l[]){
for(ll i = 0; i < n-1; i++){
v[h[i][0]].insert({h[i][1], l[i]});
v[h[i][1]].insert({h[i][0], l[i]});
}
int ans = 1e9;
queue<int>q;
q.push(0);
vector<int> d(200005,0);
while(!q.empty()){
int x = q.front();
q.pop();
n = 0;
calc(x,-1);
int root = centroid(x,-1);
map<ll,int> dist, cur, clr;
function<void(int,int,int)> dfs = [&](int x, int p, int depth){
if(cur[d[x]] = 0) cur[d[x]] = depth;
else cur[d[x]] = min(cur[d[x]], depth);
for(auto [u,w] : v[x]){
if(u != p){
d[u] = d[x] + w;
dfs(u, x, depth+1);
}
}
};
for(auto [u,w] : v[root]){
cur = clr;
d[u] = w;
dfs(u, root, 1);
for(auto [mal,y] : cur){
if(mal == k){
if(y > 0){
ans = min(ans,y);
}
}
else{
if(mal < k){
if(y > 0 and dist[k-mal] > 0){
ans = min(ans, (int)(mal + dist[k - mal]));
}
}
}
}
for(auto [w,y] : cur){
if(dist[w] == 0){
dist[w] = y;
}
else dist[w] = min(dist[w],y);
}
}
for(auto [u,y] : v[x]){
v[u].erase({root,y});
q.push(y);
}
v[root].clear();
}
if(ans == 1e9)ertunt -1;
else ertunt ans;
}
