#include<bits/stdc++.h>

using namespace std;

/*
int h[][2] = {
    {0, 1},
    {0, 2},
    {2, 3},
    {3, 4},
    {4, 5},
    {0, 6},
    {6, 7},
    {6, 8},
    {8, 9},
    {8, 10}
};
int l[] = {3,4,5,4,6,3,2,5,6,7};
*/

int h[][2] = {
    {0, 1},
    {1, 2},
};
int l[] = {1,1};

using lint = int64_t;
using pii = pair<int, int>;
using pli = pair<lint, int>;
int n, k;
pii path[1000005];
vector<vector<pli>> g;
bool vis[1000005];
int mini[1000005];
int ans, inf;
int dfs(int u, int p){
    pii child = {0, u};
    int sub = 0;
    for(auto [l, v] : g[u]){
        if(vis[v] || v == p) continue;
        int cur = dfs(v, u);
        sub += cur;
        child = max<pii>(child, {cur, v});
    }
    path[u] = child;
    return sub;
}


void dist(int u, int p, int prof, int edges, vector<pii> &count){
    if(prof > k) return;
    count.emplace_back(prof, edges);
    for(auto [l, v] : g[u]){
        if(vis[v] || v == p) continue;
        dist(v, u, prof + l, edges + 1, count);
    }
}

void decomp(int u){
    int sub = dfs(u, u);
    int c = u;
    while(path[c].first > sub/2) c = path[c].second;
    vis[c] = true;

    vector<vector<pii>> child; child.reserve(g[c].size());
    vector<pii> cur; cur.reserve(sub);
    for(auto [l, v] : g[c]){
        cur.clear();
        dist(v, c, l, 1, cur);
        for(auto [prof, edges] : cur){
            int comp = k - prof;
            if(comp >= 0)
                ans = min(ans, edges + mini[comp]);
        }
        child.push_back(cur);
        for(auto [prof, edges] : cur)
            mini[prof] = min(mini[prof], edges);
    }
    for(const auto &cur : child)
        for(auto [prof, edges] : cur)
            mini[prof] = inf;
    
    for(auto [l, v] : g[c])
        if(!vis[v])
            decomp(v);
}

int best_path(int N,int K,int H[][2], int L[]){
    inf = ans = 1000005;
    g.clear();
    g.resize(N);
    for(int u = 0; u<N; u++){
        vis[u] = false;
        mini[u] = inf;
    }
    n = N;
    k = K;
    mini[0] = 0;
    for(int i = 0; i + 1 < n; i++){
        int u = H[i][0], v = H[i][1], c = L[i];
        g[u].emplace_back(c, v);
        g[v].emplace_back(c, u);
    }
    decomp(0);
    if(ans >= inf) ans = -1;
    return ans;
}