#include <bits/stdc++.h>
#include "race.h"
//#define int long long
#define debug cout << "ok\n";
#define SQR(x) (1LL * ((x) * (x)))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pli pair<ll,int>
#define vi vector<int>
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;
using namespace std;
const int M = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);
const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
template<class _, class __>
bool minimize(_ &x, const __ y){
if(x > y){
x = y;
return true;
} else return false;
}
template<class _, class __>
bool maximize(_ &x, const __ y){
if(x < y){
x = y;
return true;
} else return false;
}
template<class _,class __>
void Add(_ &x, const __ y) {
x += y;
if (x >= M) {
x -= M;
}
return;
}
template<class _,class __>
void Diff(_ &x, const __ y) {
x -= y;
if (x < 0) {
x += M;
}
return;
}
//--------------------------------------------------------------
const int MaxN = 2e5+7;
int n,k,sz[MaxN],h[MaxN],res = INF;
long long len[MaxN];
map<long long,int> f,g;
bool isCT[MaxN];
vector<pii> a[MaxN];
void dfs(int u,int p) {
sz[u] = 1;
for (pii e : a[u]) {
int v = e.fi;
if (v == p || isCT[v]) continue;
dfs(v,u);
sz[u] += sz[v];
}
}
int GetCen(int u,int p,int r) {
for (pii e : a[u]) {
int v = e.fi;
if (v == p || isCT[v]) continue;
if (sz[v]*2 >= sz[r]) return GetCen(v,u,r);
}
return u;
}
void dfss(int u,int p) {
if (f.find(k-len[u]) != f.end()) minimize(res,f[k-len[u]] + h[u]);
if (g.find(len[u]) == g.end()) g[len[u]] = h[u];
else minimize(g[len[u]],h[u]);
for (pii e : a[u]) {
int v = e.fi;
int w = e.se;
if (v == p || isCT[v]) continue;
h[v] = h[u] + 1;
len[v] = len[u] + w;
dfss(v,u);
}
}
void CenTroid(int u) {
dfs(u,-1);
u = GetCen(u,-1,u);
isCT[u] = true;
f.clear();
f[0] = 0;
for (pii e : a[u]) {
int v = e.fi;
if (isCT[v]) continue;
g.clear();
len[v] = e.se;
h[v] = 1;
dfss(v,-1);
for (pii tmp : g) {
if (f.find(tmp.fi) == f.end()) f[tmp.fi] = tmp.se;
else minimize(f[tmp.fi],tmp.se);
}
}
for (pii e : a[u]) {
int v = e.fi;
if (isCT[v]) continue;
CenTroid(v);
}
}
int best_path(int N,int K,int h[][2],int l[]) {
k = K;
n = N;
for (int i=1;i<=n;i++) a[i].clear();
for (int i=0;i<N-1;i++) {
int u = h[i][0];
int v = h[i][1];
u++,v++;
int w = l[i];
a[u].pb(mp(v,w));
a[v].pb(mp(u,w));
}
res = INF;
CenTroid(1);
if (res >= INF) return -1;
else return res;
}
//void sol() {
//
//}
//
//signed main() {
//// freopen("test.inp","r",stdin);
//// freopen("test.out","w",stdout);
// FAST
// int t=1;
//// cin >> t;
// while (t--) sol();
//}
