#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC target("avx2")
using namespace std;
#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < vi > vvi;
const int N = 200200, A = 1000001;
int _sz[N], used[N], mn[A];
vector <vector <pii > > g(N);
void calc_sz (int v, int pr) {
_sz[v] = 1;
for (auto i : g[v]) {
int to = i.F;
if (used[to] || to == pr) {
continue;
}
calc_sz(to, v);
_sz[v] += _sz[to];
}
}
int get_centroid (int v, int pr, int n) {
for (auto i : g[v]) {
int to = i.F;
if (to == pr || used[to] || _sz[to] < n / 2) {
continue;
}
return get_centroid(to, v, n);
}
return v;
}
int n, k, ans = 1e9;
vector<pii> vec;
void dfs (int v, int pr, int w, int d) {
if (w > k) {
return;
}
int need = w - k;
if (need == 0) {
ans = min(ans, d);
}
ans = min(ans, d + mn[need]);
vec.pb({w, d});
for (auto i : g[v]) {
int to = i.F, w1 = i.S;
if (used[to] || to == pr) {
continue;
}
dfs (to, v, w + w1, d + 1);
}
}
void calc_ans (int c, int pr) {
calc_sz(c, pr);
int v = get_centroid(c, pr, _sz[c]);
used[v] = 1;
vector <pii> all_vec;
for (auto to : g[v]) {
int i = to.F, w = to.S;
if (used[i] || i == pr) {
continue;
}
dfs (i, v, w, 1);
for (auto j : vec) {
mn[j.F] = min(mn[j.F], j.S);
all_vec.pb(j);
}
vec.clear();
}
for (auto i : all_vec) {
mn[i.F] = 1e9;
}
for (auto i : g[v]) {
int to = i.F;
if (used[to] || to == pr) {
continue;
}
calc_ans(to, v);
}
}
void best_path (int N, int K, int h[][2], int l[]) {
n = N;
k = K;
for (int i = 0; i < n; i++) {
int u = h[i][0], v = h[i][1], w = l[i];
u++, v++;
g[u].pb({v, w});
g[v].pb({u, w});
}
for (int i = 0; i < A; i++) {
mn[i] = 1e9;
}
calc_ans(1, 1);
if (ans >= 1e9) {
ans = -1;
}
cout << ans;
}
/*
signed main() {
int n = 4, k = 3;
int h[]
/*ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
cout << "\n";
}
}
*/
