#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NMAX = 2e5+20;
const ll inf = 1e9;
ll n, eul[NMAX], siz[NMAX], in[NMAX], out[NMAX], edges[NMAX], timer, d[NMAX],ans,k;
vector<vector<pair<ll,ll>>> g(NMAX);
void dfs1(ll x, ll par) {
siz[x] = 1;
in[x] = timer;
eul[timer++] = x;
for(auto c : g[x]) {
ll y = c.first;
if(y==par) continue;
edges[y] = edges[x] + 1;
d[y] = d[x] + c.second;
dfs1(y, x);
siz[x] += siz[y];
}
out[x] = timer;
}
map<ll, map<ll,ll>> M;
map<ll, ll> MG;
void add(ll x, ll ancst) {
M[d[x]][edges[x]]++;
}
void remove(ll x) {
M[d[x]][edges[x]]--;
if(M[d[x]][edges[x]] == 0) M[d[x]].erase(edges[x]);
if(M[d[x]].empty())M.erase(d[x]);
}
//ll check[NMAX];
void dfs2(ll x, ll p, bool keep, ll level) {
//check[level] = x;
ll mx = -1, bigc = -1;
for(auto c : g[x]) {
ll y = c.first;
if(y == p) continue;
if(siz[y] > mx) {
mx = siz[y], bigc = y;
}
}
for(auto c : g[x]) {
ll y = c.first;
if(y != p && y != bigc) {
dfs2(y,x,0,level+1);
}
}
if(bigc != -1) {
dfs2( bigc, x, 1, level+1);
if(!M[k + d[x]].empty())ans = min(ans, (M[k + d[x]].rbegin())->first - edges[x]);
}
for(auto c : g[x]) {
ll y = c.first;
if(y != p && y != bigc) {
for(ll i = in[y]; i < out[y]; i++) {
if(k + d[x] - d[eul[i]] == 0) {
ans = min(ans, edges[eul[i]] - edges[x]);
}
else if(!M[k + d[x] - d[eul[i]]].empty()) {
ll a = edges[eul[i]], b = (M[k + d[x] - d[eul[i]]].rbegin())->first;
ans = min(ans, a + b - edges[x]);
}
add(eul[i], x);
}
}
}
add(x, p);
if(!keep) {
for(ll i = in[x]; i < out[x]; i++) {
remove(eul[i]);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
ans = inf;
k = K;
for(ll i = 0; i < n-1; i++) {
ll x = H[i][0], y = H[i][1];
g[x].push_back({y, L[i]}), g[y].push_back({x, L[i]});
}
timer = 1;
edges[0] = 0;
dfs1(0, -1);
dfs2(0, -1, 0, 0);
if(ans == inf) ans = -1;
return ans;
}
/*
ll main() {
ll N, K;
cin >> N >> K;
ll H[N][2], L[N];
n = N;
for(ll i = 0; i < N-1; i++) {
cin >> H[i][0] >> H[i][1];
}
for(ll i = 0; i < N-1; i++) {
cin >> L[i];
}
for(ll i = 0; i < N-1; i++) {
ll x = H[i][0], y = H[i][1];
g[x].push_back({y, L[i]}), g[y].push_back({x, L[i]});
}
timer = 1;
edges[0] = 0;
k = K;
dfs1(0, -1);
ans = inf;
for(ll i = 0; i < n; i++) {
prllf("%d %d %d\n", i, edges[i], d[i]);
}
dfs2(0, -1, 0, 0);
prllf("here %d\n", ans);
}
*/
