#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
//#include "dreaming.h"
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;
const int MAXN = 2e5 + 11;
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;
/*
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
if ((name.size())) {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
}
*/
vector<pair<int,ll>> adj[MAXN];
ll n, k;
int sz[MAXN];
bool vis[MAXN];
int mp[1000100];
vector<ll> to_del;
map<ll, bool> used;
int ans = 1e9;
void dfs(int v, int p,bool fill,ll sum,int len)
{
if (sum > k)
return;
if (fill)
{
to_del.push_back(sum);
if (used[sum] == 0)
mp[sum] = len, used[sum] = true;
else
mp[sum] = min(mp[sum], len);
}
else
{
ll need = k - sum;
//cout << v << " " << sum << " " << len <<
// " and " << need << " " << mp[need] << '\n';
if (need == 0 || mp[need] != 0)
ans = min(ans, mp[need] + len);
}
for (auto u : adj[v])
{
if (u.first == p || vis[u.first])
continue;
dfs(u.first, v, fill, sum + u.second, len + 1);
}
}
int find_size(int v, int p)
{
if (vis[v])
return 0;
sz[v] = 1;
for (auto u : adj[v])
{
if (u.first == p)
continue;
sz[v] += find_size(u.first, v);
}
return sz[v];
}
int find_centroid(int v, int p,int n)
{
for (auto u : adj[v])
{
if (u.first == p || vis[u.first])
continue;
if (sz[u.first] > n / 2)
return find_centroid(u.first, v, n);
}
return v;
}
void decomp(int v, int p)
{
find_size(v, -1);
int c = find_centroid(v, -1, sz[v]);
vis[c] = true;
to_del.clear();
for (auto u : adj[c])
{
if (vis[u.first])
continue;
dfs(u.first, -1, 0, u.second, 1);
dfs(u.first, -1, 1, u.second, 1);
}
for (auto vals : to_del)
{
mp[vals] = 0;
used[vals] = false;
}
for (auto u : adj[c])
{
if (vis[u.first])
continue;
decomp(u.first, c);
}
}
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 v = h[i][0]+1;
int u = h[i][1]+1;
int cost = l[i];
adj[u].push_back({ v,cost });
adj[v].push_back({ u,cost });
}
decomp(1, -1);
if (ans == 1e9)
ans = -1;
return ans;
}
/*
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
//setIO("movie");
cin >> n >> k;
for(int i =1;i<n;i++)
{
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({ b,c });
adj[b].push_back({ a,c });
}
decomp(1, -1);
if (ans == 1e9)
cout << -1 << '\n';
else
cout << ans << '\n';
return 0;
}
*/
