#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, k, ans = maxn;
vector<bool> alive(maxn, true);
vector<int> siz(maxn, 0);
vector<vector<pair<int, int> > > g(maxn);
void dfs_size(int u, int p = -1)
{
siz[u] = 1;
for (pair<int, int> i : g[u])
{
if (!alive[i.first] || i.first == p) continue;
dfs_size(i.first, u);
siz[u] += siz[i.first];
}
}
int dfs_centroid(int u, int s, int p = -1)
{
for (const pair<int, int> &i : g[u])
{
if (!alive[i.first] || i.first == p) continue;
if (siz[i.first] > s/2) return dfs_centroid(i.first, s, u);
}
return u;
}
void dfs_dist(int u, vector<pair<int, int> > &v, int depth = 0, int dist = 0, int p = -1)
{
if (dist == k) return (void)(ans = min(ans, depth));
if (dist > k) return;
v.push_back({dist, depth});
for (pair<int, int> i : g[u])
{
if (!alive[i.first] || i.first == p) continue;
dfs_dist(i.first, v, depth+1, dist+i.second, u);
}
}
void centroid_decomp(int r)
{
dfs_size(r);
int u = dfs_centroid(r, siz[r]);
map<int, int> m;
alive[u] = false;
for (const pair<int, int> &i : g[u])
{
if (!alive[i.first]) continue;
centroid_decomp(i.first);
vector<pair<int, int> > v;
dfs_dist(i.first, v, 1, i.second, u);
for (const pair<int, int> &j : v)
{
//cout << m.count(k-j.first) << " " << m[k-j.first] << "\n";
if (m.count(k-j.first))
ans = min(ans, j.second+m[k-j.first]);
}
for (const pair<int, int> &j : v)
if (!m.count(j.first))
m[j.first] = j.second;
else
m[j.first] = min(m[j.first], j.second);
//cout << "\n" << u << "\n";
//for (pair<int, int> j : m) cout << j.first << " " << j.second << "\n";
}
alive[u] = true;
}
int best_path(int N, int K, int e[][2], int l[])
{
n = N, k = K;
for (int i = 0; i < n-1; i++)
{
g[e[i][0]].push_back({e[i][1], l[i]});
g[e[i][1]].push_back({e[i][0], l[i]});
}
centroid_decomp(0);
return ans == maxn ? -1 : ans;
}
