#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};

using lint = int64_t;
using pii = pair<int, int>;
using pli = pair<lint, int>;
int n, k;
vector<pii> path;
vector<vector<pli>> g;
vector<bool> vis;
vector<int> mini;
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;
    for(auto [l, v] : g[c]){
        vector<pii> cur;
        dist(v, c, l, 1, cur);
        for(auto [prof, edges] : cur){
            int comp = k - prof;
            if(comp >= 0)
                ans = min(ans, edges + mini[comp]);
            mini[prof] = min(mini[prof], edges);
        }
        child.push_back(cur);
    }
    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 = N;
    path.resize(N);
    g.clear();
    g.resize(N);
    vis.resize(N);
    n = N;
    k = K;
    mini.assign(K+1, inf);
    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);
    return ans;
}