#include "race.h"
#include <bits/stdc++.h>
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define type(x) __typeof(x.begin())
#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)
#define pb push_back
#define mp make_pair
#define nd second
#define st first
#define endl '\n'
using namespace std;
#define pii pair < int ,int >
const int N = 1e6 + 5;
const int inf = 1e9 + 7;
int ans = inf;
int k, H[N], h[N], n, m, x, y, t, S, sum[N];
vector< pii > v[N], g[N];
int prep(int node, int root) {
sum[node] = 1;
foreach(it, v[node])
if(!h[it->st] && it->st != root)
sum[node] += prep(it->st, node);
return sum[node];
}
int find(int node, int root) {
foreach(it, v[node])
if(!h[it->st] && it->st != root && sum[it->st] > S)
return find(it->st, node);
return node;
}
void dfs(int node, int root, int dist, int S, int t) {
if(dist > k) return ;
g[S].pb(mp(dist, t));
foreach(it, v[node])
if(it->st != root && !h[it->st])
dfs(it->st, node, it->nd + dist, S, t + 1);
}
void solve(int node) {
prep(node, 0); S = sum[node] >> 1;
node = find(node, 0);
h[node] = 1;
S = 0;
foreach(it, v[node]) {
if(!h[it->st]) {
g[++S].clear();
dfs(it->st, node, it->nd, S, 1);
}
}
H[0] = 0;
FOR(i, 1, S) {
foreach(it, g[i])
if(it->st <= k)
ans = min(H[k-it->st] + it->nd, ans);
foreach(it, g[i])
if(it->st <= k)
H[it->st] = min(H[it->st], it->nd);
}
H[0] = inf;
FOR(i, 1, S)
foreach(it, g[i])
if(it->st <= k)
H[it->st] = inf;
foreach(it, v[node])
if(!h[it->st])
solve(it->st);
}
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],
y = H[i][1];
v[x].pb(mp(y, L[i]));
v[y].pb(mp(x, L[i]));
}
memset(::H, 10, sizeof ::H);
ans = inf;
solve(1);
if(ans > n) ans = -1;
return ans;
}
