#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
#include "race.h"
/*
1.BFS numer of children (priority queue with visited)
2.Check children nodes with each other (set with upper and lower bound)
3.Save children distances to the parent node (save a set with distances to each leaf)
*/
// vector<vpi> paths(2e5+3,vpi());
// vector<vector<vpi>> dist(2e5+3,vector<vpi>(102,vpi()));
// // vpi dist[200003][102];
// vi children(2e5+3);
// vi parent(2e5+3,-1);
// vi parent_dist(2e5+3,-1);
vector<vpi> paths;
// vector<vector<vpi>> dist;
// vpi dist[200003][102];
vi children;
vi parent;
vi parent_dist;
void dfs(int pos,int prev){
int sum = 1;
for(auto node:paths[pos]){
if(node.F == prev)continue;
parent[node.F] = pos;
parent_dist[node.F] = node.S;
dfs(node.F,pos);
sum += children[node.F];
}
children[pos] = sum;
}
int best_path(int N, int K, int H[][2], int L[])
{
paths = vector<vpi>(N,vpi());
vector<vector<vpi>> dist = vector<vector<vpi>>(N,vector<vpi>(101,vpi(2,{1e9,-1})));
children = vi (N);
parent = vi (N,-1);
parent_dist = vi (N,-1);
FOR(i,0,N-1){
paths[H[i][0]].pb({H[i][1],L[i]});
paths[H[i][1]].pb({H[i][0],L[i]});
}
dfs(0,-1);
// FOR(i,0,N)cout << children[i] << " ";
// cout << endl;
// FOR(i,0,N)cout << parent[i] << " ";
// cout << endl;
// FOR(i,0,N)cout << parent_dist[i] << " ";
// cout << endl;
priority_queue<pi> pq;
FOR(i,0,N){
pq.push({-children[i],i});
}
int ans = 1e9;
while(!pq.empty()){
int node = pq.top().S;pq.pop();
// cout << node << " | " << endl;
FOR(j,0,55){
if(dist[node][j][0].F != 1e9){
pi a = dist[node][j][0];
FOR(l,0,2){
if(dist[node][K-j][l].F != 1e9){
if(dist[node][K-j][l].S != a.S){
ans = min(ans,a.F+dist[node][K-j][l].F+1);
}
}
}
}
}
if(parent[node] == -1)continue;
// cout << "b " << endl;
if(parent_dist[node] == K){
// cout << "2 ans - " << 2 << endl;
ans = min(ans, 2);
}
if(parent_dist[node] <= K){
if(dist[parent[node]][parent_dist[node]][0].F > 1){
swap(dist[parent[node]][parent_dist[node]][0],dist[parent[node]][parent_dist[node]][1]);
dist[parent[node]][parent_dist[node]][0] = {1,node};
}else if(dist[parent[node]][parent_dist[node]][1].F > 1){
dist[parent[node]][parent_dist[node]][1] = {1,node};
}
}
// cout << "c" << endl;
FOR(j,0,101){
if(dist[node][j][0].F != 1e9){
pi a = dist[node][j][0];
if(parent_dist[node]+j == K){
ans = min(ans, a.F+2);
}
if(parent_dist[node]+j >= K)continue;
if(dist[parent[node]][parent_dist[node]+j][0].F > a.F+1){
swap(dist[parent[node]][parent_dist[node]+j][0],dist[parent[node]][parent_dist[node]+j][1]);
dist[parent[node]][parent_dist[node]+j][0] = {a.F+1,node};
}
else if(dist[parent[node]][parent_dist[node]+j][1].F > a.F+1){
dist[parent[node]][parent_dist[node]+j][1] = {a.F+1,node};
}
// cout << "d" << endl;
}
// cout << "e" << endl;
// FOR(k,0,dist[node][j].size()){
// pi a = dist[node][j][k];
// // cout << "c " << parent[node] << " " << parent_dist[node]+a.F << " " << a.S.F+1 << " " << node << endl;
// if(parent_dist[node]+j == K){
// // cout << " 2 ans - " << a.S.F+2 << endl;
// ans = min(ans, a.F+2);
// }
// if(parent_dist[node]+j >= K)continue;
// dist[parent[node]][parent_dist[node]+j].pb({a.F+1,node});
// }
}
// cout << endl;
}
if(ans == 1e9)return -1;
return ans-1;
}
