#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <array>
#include <cassert>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MK make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
vector<pii> edge[MAX];
int cnt[MAX], vis[MAX], w[MAX];
int n, k, half;
int ans = 2e9;
map<ll, int> dis;
void dfs(int now, int from){
cnt[now] = 1;
for(pii y : edge[now]){
int i = y.F;
if(i == from || vis[i])
continue;
dfs(i, now);
cnt[now] += cnt[i];
}
}
int find(int now, int from){
for(pii y : edge[now]){
int i = y.F;
if(i == from || vis[i])
continue;
if(cnt[i] > half)
return find(i, now);
}
return now;
}
void calc1(int now, int from, int d, ll val){
if(val > k)
return;
if(dis.count(k - val)){
ans = min(ans, d + dis[k - val]);
}
for(pii y: edge[now]){
int i = y.F;
if(vis[i] || i == from)
continue;
calc1(i, now, d + 1, val + y.S);
}
}
void calc2(int now, int from, int d, ll val){
if(val > k){
return;
}
if(dis.count(val) != 0){
dis[val] = min(dis[val], d);
}else{
dis[val] = d;
}
for(pii y : edge[now]){
int i = y.F;
if(vis[i] || i == from)
continue;
calc2(i, now, d + 1, val + y.S);
}
}
void solve(int x){
dfs(x, x);
half = cnt[x] / 2;
int c = find(x, x);
vis[c] = 1;
dis[0] = 0;
for(pii i : edge[c]){
int y = i.F;
if(!vis[y]){
calc1(y, y, 1, i.S);
calc2(y, y, 1, i.S);
}
}
dis.clear();
for(pii i : edge[c]){
if(!vis[i.F])
solve(i.F);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0;i < n - 1;i++){
edge[H[i][0]].PB(MK(H[i][1], L[i]));
edge[H[i][1]].PB(MK(H[i][0], L[i]));
}
solve(0);
return (ans == 2e9 ? -1 : ans);
}
// int main(){
// IOS
// int N, K;
// cin >> N >> K;
// int H[N - 1][2], L[N - 1];
// for(int i = 0;i < N - 1;i++){
// cin >> H[i][0] >> H[i][1];
// }
// for(int i = 0;i < N - 1;i++)
// cin >> L[i];
// cout << best_path(N, K, H, L) << '\n';
// return 0;
// }
