//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NMAX = 2e5+20;
const ll inf = 1e18;
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;
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]);
//printf("removing %d\n", x);
}
//ll check[NMAX];
void dfs2(ll x, ll p, bool keep, ll level) {
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]].begin())->first - edges[x]);
}
}
stack<int> v;
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 + 2 * d[x] - d[eul[i]] == 0) {
ans = min(ans, edges[eul[i]] - edges[x]);
}
else if(!M[k + 2 * d[x] - d[eul[i]]].empty()) {
ll a = edges[eul[i]], b = (M[k + 2 * d[x] - d[eul[i]]].begin())->first;
ans = min(ans, a + b - 2 * edges[x]);
}
v.push(eul[i]);
}
while(!v.empty()) {
add(v.top(), x);
v.pop();
}
}
}
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;
}
/*
int 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] >> 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;
dfs2(0, -1, 0, 0);
printf("%lld\n", ans);
}
*/
