#include "race.h"
# include <bits/stdc++.h>
using namespace std;
# define x first
# define y second
# define ll long long
# define vi vector < int >
# define vl vector < ll >
# define pii pair < int , int >
# define mp make_pair
# define vii vector < pii >
# define pb push_back
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int best_path(int N, int K, int H[][2], int L[])
{
static vii g[1 << 20];
int n = N;
for (int i = 0;i < n - 1;++i)
g[H[i][0] + 1].pb(mp(H[i][1] + 1,L[i])),
g[H[i][1] + 1].pb(mp(H[i][0] + 1,L[i]));
int ans = 1e9;
static int S[1 << 20];
static int was[1 << 20];
static int vv[1 << 20];
static int D[1 << 20];
for (int i = 1;i <= n;++i)
was[i] = 1;
for (int i = 1;i <= 1e6 + 5;++i)
D[i] = -1;
vi us;
function < void(int,int) > dfs1 = [&](int node,int prev)
{
vv[node] = 0;
us.pb(node);
S[node] = 1;
for (auto it : g[node])
if (vv[it.x] && was[it.x])
dfs1(it.x,node),S[node] += S[it.x];
};
vi vis;
function < void(int,int,int,int) > dfs2 = [&](int node,int prev,int sum,int dep)
{
if (sum > K)
return;
vis.pb(sum);
if (D[K - sum] != -1)
smin(ans,D[K - sum] + dep);
for (auto it : g[node])
if (it.x != prev && was[it.x])
dfs2(it.x,node,sum + it.y,dep + 1);
};
function < void(int,int,int,int) > dfs3 = [&](int node,int prev,int sum,int dep)
{
if (sum > K)
return;
if (D[sum] == -1 || D[sum] > dep)
D[sum] = dep;
for (auto it : g[node])
if (it.x != prev && was[it.x])
dfs3(it.x,node,sum + it.y,dep + 1);
};
while (*max_element(was + 1,was + 1 + n))
{
for (int i = 1;i <= n;++i)
vv[i] = 1;
for (int i = 1;i <= n;++i)
if (vv[i] && was[i])
{
vis.clear();
us.clear();
dfs1(i,0);
const int sz = us.size();
pii mx = mp(n + 5,0);
for (auto vertex : us)
{
int mm = 0;
for (auto it : g[vertex])
if (was[it.x] && S[it.x] < S[vertex])
smax(mm,S[it.x]);
smax(mm,sz - S[vertex]);
smin(mx,mp(mm,vertex));
}
int vertex = mx.y;
for (auto it : g[vertex])
if (was[it.x])
{
dfs2(it.x,vertex,it.y,1);
dfs3(it.x,vertex,it.y,1);
}
was[vertex] = 0;
for (auto it : vis)
D[it] = -1;
}
}
if (ans == 1e9)
ans = -1;
return ans;
}
