#include <bits/stdc++.h>
#include "race.h"
using namespace std;
// KACTL TEMPLATE
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
const int N = 100 + 5;
const int D = 100 + 5;
int sz[N];
bool vis[N];
int dis[D];
vector<pii> adj[N];
int best_path(int n, int k, int h[][2], int l[]) {
for (int i = 0; i < n - 1; i++) {
int u = h[i][0];
int v = h[i][1];
int w = l[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
int ans = -1;
auto dfs = [&](auto &&self, int u, int p) -> void {
sz[u] = 1;
for (auto &[v, w]: adj[u]) {
if (vis[v] || v == p) {
continue;
}
self(self, v, u);
sz[u] += sz[v];
}
};
auto get_root = [&](auto &&self, int u, int p, int &s) -> int {
for (auto &[v, w]: adj[u]) {
if (vis[v] || v == p) {
continue;
}
if (sz[v] * 2 > s) {
return self(self, v, u, s);
}
}
return u;
};
auto calc = [&](auto &&self, int u, int d, int s, vector<pii> &add) -> void {
if (s > k) {
return;
}
add.emplace_back(s, d);
if (dis[k - s] != -1) {
if (ans == -1) {
ans = dis[k - s] + d;
} else {
ans = min(ans, dis[k - s] + d);
}
}
for (auto &[v, w]: adj[u]) {
if (vis[v]) {
continue;
}
self(self, v, d + 1, s + w, add);
}
};
auto solve = [&](auto &&self, int u) -> void {
dfs(dfs, u, -1);
int r = get_root(get_root, u, -1, sz[u]);
vis[r] = true;
dis[0] = 0;
vi ls;
for (auto &[v, w]: adj[r]) {
if (vis[v]) {
continue;
}
vector<pii> add;
calc(calc, v, 1, w, add);
for (auto &[s, d]: add) {
if (dis[s] == -1) {
dis[s] = d;
} else {
dis[s] = min(dis[s], d);
}
ls.push_back(s);
}
}
for (int s: ls) {
dis[s] = -1;
}
for (auto &[v, w]: adj[r]) {
if (!vis[v]) {
self(self, v);
}
}
};
memset(dis, -1, sizeof dis);
solve(solve, 0);
return ans;
}
