#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int best_path(int n, int k, int edges[][2], int wt[])
{
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; i++)
{
int u = edges[i][0], v = edges[i][1], w = wt[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<int> depth(n);
vector<ll> dis(n);
function<void(int, int, int)> dfs = [&](int u, int p, int d)
{
depth[u] = d;
for (auto [v, w] : g[u])
{
if (v == p)
continue;
dis[v] = dis[u] + w;
dfs(v, u, d + 1);
}
};
dfs(0, -1, 0);
vector<map<ll, int>> paths(n);
for (int i = 0; i < n; i++)
paths[i][dis[i]] = depth[i];
int minPaths = n + 1;
auto merge = [&](map<ll, int> &a, map<ll, int> &b, int u, int v) -> void
{
if (a.size() < b.size())
swap(a, b);
for (auto [netDist, netDepth] : b)
{
// a + b - 2 * me = k
// a = k + 2 * me - b
ll key = k + 2LL * dis[u] - netDist;
if (a.count(key))
minPaths = min(minPaths, a[key] + netDepth - 2 * depth[u]);
}
for (auto [netDist, netDepth] : b)
{
if (a.count(netDist))
a[netDist] = min(a[netDist], netDepth);
else
a[netDist] = netDepth;
}
};
function<void(int, int)> dfs2 = [&](int u, int p)
{
for (auto [v, w] : g[u])
{
if (v == p)
continue;
dfs2(v, u);
merge(paths[u], paths[v], u, v);
}
};
dfs2(0, -1);
return minPaths == n + 1 ? -1 : minPaths;
}
