#include "race.h"
//{
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
_s<<"{";
for(It _it=_ita;_it!=_itb;_it++)
{
_s<<(_it==_ita?"":",")<<*_it;
}
_s<<"}";
return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}
const ll MAXn=2e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e9);
namespace pre{
vector<ii> v[MAXn];
ii p[MAXn];
ll lf[MAXn];
void dfs(ll now, ll f)
{
lf[now] = 1;
for(ii k:v[now])if(k.X != f)
{
p[k.X] = ii(now, k.Y);
lf[now] = 0;
dfs(k.X, now);
}
}
};
ll ans = INF, n, k;
void cal(vector<ii> &a, vector<ii> &b)
{
ll it = SZ(b) - 1;
REP(i, SZ(a))
{
while(it >= 0 && a[i].X + b[it].X > k)it --;
if(it >= 0 && a[i].X + b[it].X == k)ans = min(ans, a[i].Y + b[it].Y);
}
}
vector<ii> mg(vector<ii> &a, vector<ii> &b, ii d)// merge (a, b + d)
{
for(auto &p:b)p.X = min(INF, p.X + d.X), p.Y += d.Y;
vector<ii> c(SZ(a) + SZ(b));
merge(ALL(a), ALL(b), c.begin());
vector<ii> ret;
for(auto &p:c)if(!SZ(ret) || p.X != ret.back().X)ret.pb(p);
return ret;
}
ll u[MAXn], gct;
ii dis[MAXn];
vector<ll> v[MAXn];
vector<ii> dt[MAXn][2];
#define CLR(_a) (_a).clear(),(_a).shrink_to_fit()
void dfs(ll now)
{
u[now] = 0;
for(ll t:v[now])dfs(t);
if(SZ(v[now]) == 1)
{
ll t = v[now][0];
if(u[t] || now == 0)return;
u[t] = u[now] = 1;
gct --;
cal(dt[t][0], dt[now][1]);
dt[now][0] = mg(dt[now][0], dt[t][0], dis[now]);
if(SZ(v[t])){
dt[now][1] = mg(dt[t][1], dt[now][1], dis[t]);
dis[now] = {dis[now].X + dis[t].X, dis[now].Y + dis[t].Y};
}
v[now] = v[t];
CLR(v[t]);CLR(dt[t][0]);CLR(dt[t][1]);
return;
}
vector<ll> a, b, nv;
for(ll t:v[now])
{
if(u[t])nv.pb(t);
else if(!SZ(v[t]))a.pb(t);
else b.pb(t);
}
for(int i = 0;i < SZ(a);)
{
ll x, y;
if(i < SZ(b))x = b[i], y = a[i], i ++;
else if(i < SZ(a) - 1)x = a[i + 1], y = a[i], i += 2;
else{
nv.pb(a[i]);
break;
}
u[x] = u[y] = 1;
gct --;
nv.pb(x);
cal(dt[x][0], dt[y][0]);
dt[x][0] = mg(dt[x][0], dt[y][0], {0, 0});
if(SZ(v[x]))dt[x][1] = mg(dt[x][1], dt[y][0], dis[x]);
CLR(v[y]);CLR(dt[y][0]);CLR(dt[y][1]);
}
if(SZ(b) > SZ(a))for(int i = SZ(a);i < SZ(b);i ++)nv.pb(b[i]);
v[now] = nv;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
n = N;
REP(i, n - 1)
{
pre::v[H[i][0]].pb(ii(H[i][1], L[i]));
pre::v[H[i][1]].pb(ii(H[i][0], L[i]));
}
pre::dfs(0, -1);
for(int i = 1;i < n;i ++)
{
v[pre::p[i].X].pb(i);
if(pre::p[i].Y == k)ans = 1;
dis[i] = {pre::p[i].Y, 1};
dt[i][0].pb({pre::p[i].Y, 1});
if(!pre::lf[i])dt[i][1].pb({pre::p[i].Y, 1});
}
gct = n - 1;
ll iter = 0;
while(gct > 1)
{
dfs(0);
iter ++;
}
debug(iter);
assert(iter <= 35);
if(ans == INF)return -1;
else return ans;
}
