#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int maxk=1e6+5;
int dl[maxn],mn[maxk],d[maxn],k,cnt,sz[maxn],sm[maxn];
vector<array<int,2>>v[maxn];
void in(int x,int p)
{
cnt++;
sz[x]=1;
for(auto [i,_]:v[x])
{
if(dl[i]||i==p)continue;
in(i,x);
sz[x]+=sz[i];
}
}
int cn(int x,int p)
{
for(auto [i,_]:v[x])
{
if(!dl[i]&&i!=p&&sz[i]>cnt/2)return cn(i,x);
}
return x;
}
void dfs1(int x,int p)
{
for(auto [i,vl]:v[x])
{
if(dl[i]||i==p)continue;
d[i]=d[x]+1;
sm[i]=sm[x]+vl;
dfs1(i,x);
}
}
int dfs2(int x,int p)
{
int s=-1;
if(mn[k-sm[x]]!=1e9)s=(mn[k-sm[x]]+d[x]);
for(auto [i,_]:v[x])
{
if(dl[i]||i==p||sm[i]>k)continue;
int vl2=dfs2(i,x);
// cout<<vl2<<' '<<s<<' '<<sm[x]<<' '<<mn[k-sm[i]]<<endl;
}
return s;
}
void dfs3(int x,int p)
{
mn[sm[x]]=min(d[x],mn[sm[x]]);
for(auto [i,_]:v[x])if(!dl[i]&&i!=p&&sm[i]<=k)dfs3(i,x);
}
int rt(int x)
{
d[x]=mn[0]=sm[x]=0;
dfs1(x,x);
int rtr=-1;
for(auto [j,_]:v[x])if(!dl[j])
{
int l=dfs2(j,x);
dfs3(j,x);
if(rtr==-1||(l<rtr&&l!=-1))rtr=l;
}
// cout<<x<<' '<<rtr<<endl;
return rtr;
}
int dcomp(int x)
{
cnt=0;
for(int x=0;x<=k;x++)mn[x]=1e9;
in(x,x);
int i=cn(x,x);
// cout<<x<<endl;
int rtr=rt(i);
dl[i]=1;
for(auto [j,_]:v[i])if(!dl[j])
{
int l=dcomp(j);
if(rtr==-1||(l<rtr&&l!=-1))rtr=l;
}
return rtr;
}
