#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int N, K;
map<long long, int> mp[100005];
vector<pii> adj[100005];
long long dist[100005];
int cnt[100005];
int ans = 1000000;
void DFS(int u, int p = N) {
int v, w;
mp[u][dist[u]] = cnt[u];
for(pii now : adj[u]) {
v = now.second, w = now.first;
if(v == p) continue;
dist[v] = dist[u] + w;
cnt[v] = cnt[u] + 1;
DFS(v, u);
if(mp[v].size() > mp[u].size()) swap(mp[v], mp[u]);
}
long long jarak;
// cout << u << " -> " << dist[u] << " " << cnt[u] << "\n";
for(pii now : adj[u]) {
v = now.second;
if(v == p) continue;
// cout << v << ":\n";
for(pii it : mp[v]) {
jarak = dist[u] * 2 + K - it.first;
if(mp[u].count(jarak)) {
ans = min(ans, mp[u][jarak] + it.second - cnt[u] * 2);
}
if(mp[u].count(it.first)) mp[u][it.first] = min(mp[u][it.first], it.second);
else mp[u][it.first] = it.second;
}
mp[v].clear();
}
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n, K = k;
for(int i = 0; i < N - 1; i++) {
adj[H[i][0]].emplace_back(L[i], H[i][1]);
adj[H[i][1]].emplace_back(L[i], H[i][0]);
}
DFS(0);
if(ans == 1000000) return -1;
return ans;
}
