#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef ljuba
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
const char nl = '\n';
#include "race.h"
const int mxN = 2e5 + 12;
int N;
ll k;
//prvi oznacava sumu duzina, drugi drugo
unordered_map<int, pll> dist[mxN];
unordered_map<int, int> dist2[mxN];
set<pii> adj[mxN];
int sub[mxN];
int ans = 1e9;
void dfs(int s, int p = -1) {
sub[s] = 1;
for(auto e : adj[s]) {
if(e.fi == p)
continue;
dfs(e.fi, s);
sub[s] += sub[e.fi];
}
}
int centroid(int s, int p, int n) {
for(auto e : adj[s]) {
if(e.fi == p)
continue;
if(sub[e.fi] > n/2)
return centroid(e.fi, s, n);
}
return s;
}
vpii tmp;
void dfs2(int s, int c, int p) {
dbg(s, c, p, dist[c][p]);
tmp.pb(dist[c][s]);
for(auto e : adj[s]) {
if(e.fi == p)
continue;
//dbg(s);
dist[c][e.fi] = {dist[c][s].fi + e.se, dist[c][s].se + 1};
int treba = k - dist[c][e.fi].fi;
if(dist2[c].count(treba)) {
ckmin(ans, (int)dist[c][e.fi].se + dist2[c][treba]);
}
dfs2(e.fi, c, s);
}
}
void build(int s) {
dfs(s);
int n = sub[s];
int c = centroid(s, -1, n);
dbg(c);
/*
dist[c].reserve(1024);
dist[c].max_load_factor(0.25);
dist2[c].reserve(1024);
dist2[c].max_load_factor(0.25);
*/
dist[c][c] = {0, 0};
dist2[c][0] = 0;
for(auto e : adj[c]) {
tmp.clear();
dist[c][e.fi] = {e.se, 1};
//tmp.pb(dist[c][e.fi]);
//ker.pb(e.fi);
if(dist2[c].count(k-e.se)) {
ckmin(ans, 1 + dist2[c][k-e.se]);
}
dfs2(e.fi, c, c);
for(auto z : tmp) {
if(!dist2[c].count(z.fi)) {
dist2[c][z.fi] = z.se;
}
ckmin(dist2[c][z.fi], z.se);
}
dbg(tmp);
}
if(dist2[c].count(k)) {
ckmin(ans, dist2[c][k]);
}
dbg(dist[c], dist2[c]);
dist[c].clear();
dist2[c].clear();
vpii temp(all(adj[c]));
for(auto z : temp) {
int b = z.fi;
int w = z.se;
adj[c].erase({b, w});
adj[b].erase({c, w});
build(b);
}
}
int best_path(int _N, int K, int H[][2], int L[]) {
N = _N;
k = K;
for(int i = 0; i < N-1; ++i) {
int a = H[i][0], b = H[i][1];
int w = L[i];
adj[a].insert({b, w});
adj[b].insert({a, w});
}
build(0);
dbg(dist[2][0]);
return (ans == 1e9 ? -1 : ans);
}
