#include "race.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(long long x, long long p, vector<vector<pair<long long, long long>>> &AR, map<long long, long long> &dp, long long K, long long prof, long long prof2, long long &best)
{
map<long long, long long> M;
M[prof] = prof2;
for (long long i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
continue;
dfs(AR[x][i].first, x, AR, dp, K, prof + AR[x][i].second, prof2 + 1, best);
if (dp.size() > M.size())
swap(dp, M);
for (auto j : dp)
{
if (M.count(K - j.first + 2 * prof))
best = min(best, M[K - j.first + 2 * prof] + j.second - 2 * prof2);
}
for (auto j : dp)
{
if (j.first - prof > K)
continue;
if (M[j.first] == 0)
M[j.first] = 100000000;
M[j.first] = min(M[j.first], j.second);
}
}
swap(dp, M);
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<long long, long long>>> AR(N);
for (long long i = 0; i < N - 1; i++)
{
AR[H[i][0]].push_back({H[i][1], L[i]});
AR[H[i][1]].push_back({H[i][0], L[i]});
};
map<long long, long long> dp;
long long best = 100000000;
dfs(0, 0, AR, dp, K, 1, 1, best);
return ((best == 100000000) ? -1 : (int)best);
}
/*int main()
{
int N, K;
cin >> N >> K;
int L[N], H[N][2];
for (long long i = 0; i < N - 1; i++)
{
// cin >> H[i][0] >> H[i][1];
H[i][0] = i, H[i][1] = i + 1;
}
for (long long i = 0; i < N - 1; i++)
{
// cin >> L[i];
L[i] = 1000000;
}
cout << best_path(N, K, H, L);
}*/
