#include <bits/stdc++.h>
#include <race.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
//#define IOS cin.tie(0)->sync_with_stdio(false);
//#define PROB "IOI11_race"
//void Fi(){
// if(fopen(PROB".inp", "r")){
// freopen(PROB".inp", "r", stdin);
// freopen(PROB".out", "w", stdout);
// }
//}
const int INF = 1e9;
const int N = 2e5 + 1;
const int K = 1e6 + 1;
vector<int> adj[N], wei[N];
int ans, RLen;
bool chking[N];
int Q[N];
int par[N], len[N], dep[N], sz[N];
int bfs(int s){
int cur, top = 0;
Q[++top] = s;
par[top] = 0;
len[top] = dep[top] = 0;
sz[top] = 1;
while(cur < top){
int u = Q[++cur];
FOR(i, 0, adj[u].size()){
if(!chking[adj[u][i]] && Q[par[cur]] != adj[u][i]){
Q[++top] = adj[u][i];
par[top] = cur;
len[top] = len[cur] + wei[u][i];
dep[top] = dep[cur] + 1;
sz[top] = 1;
}
}
}
FORD(i, top, 2) sz[par[i]] += sz[i];
return top;
}
int properCentroid(int n){
int m = N, c;
FORU(i, 1, n){
if(m > sz[i] && sz[i] > n / 2){
m = sz[i];
c = Q[i];
}
}
return c;
}
int mnE[K], upd[N];
void dfs(int s){
int n = bfs(s);
if(n == 1) return;
int c = properCentroid(n), cnt = 0;
chking[c] = true;
FOR(i, 0, adj[c].size()){
if(!chking[adj[c][i]]) dfs(adj[c][i]);
}
FOR(i, 0, adj[c].size()){
if(chking[adj[c][i]]) continue;
n = bfs(adj[c][i]);
FORU(j, 1, n){
len[j] += wei[c][i], dep[j] += 1;
if(len[j] > RLen) continue;
if(len[j] == RLen) ans = min(ans, dep[j]);
else if(mnE[RLen - len[j]]){
ans = min(ans, dep[j] + mnE[RLen - len[j]]);
}
}
FORU(j, 1, n){
if(len[j] <= RLen && (mnE[len[j]] == 0 || mnE[len[j]] > dep[j])){
mnE[len[j]] = dep[j];
upd[++cnt] = len[j];
}
}
}
chking[c] = false;
FORU(i, 1, cnt) mnE[upd[i]] = 0;
}
int best_path(int N, int K, int H[][2], int L[]){
RLen = K;
FOR(i, 0, N - 1){
adj[H[i][0]].eb(H[i][1]);
adj[H[i][1]].eb(H[i][0]);
wei[H[i][0]].eb(L[i]);
wei[H[i][1]].eb(L[i]);
}
ans = INF;
dfs(0);
return (ans != INF) ? ans : -1;
}
//int n, k, H[N][2], L[N];
//
//int main(){
// IOS;
// Fi();
// cin >> n >> k;
// FOR(i, 0, n - 1){
// cin >> H[i][0] >> H[i][1];
// }
// FOR(i, 0, n - 1) cin >> L[i];
// cout << best_path(n, k, H, L);
// return 0;
//}
