#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
int n, k;
vector<pii> g[200010];
bool v[200010];
int res=1e9;
int subtask_2(int s, int l, int h){
int res=1e9;
if(l>k){
v[s]=false;
return res;
}
if(l==k){
v[s]=false;
return h;
}
v[s]=true;
for(pii pr:g[s]){
int u=pr.ft, d=pr.sc;
if(!v[u]){
res=min(subtask_2(u, l+d, h+1), res);
}
}
v[s]=false;
return res;
}
map<pii, int> h;
int sz[200010];
void build_sz(int s){
v[s]=true;
sz[s]=1;
for(pii u:g[s]){
if(!v[u.ft]){
build_sz(u.ft);
sz[s]+=sz[u.ft];
}
}
v[s]=false;
return;
}
pii find_centroids(int s, int total){
v[s]=true;
int mx=0, u=s;
for(pii node:g[s]){
if( (sz[node.ft]>mx) && (!v[node.ft]) ){
mx=sz[node.ft];
u=node.ft;
}
if( (v[node.ft]) && ( (total-sz[s])>mx ) ){
mx=(total-sz[s]);
u=node.ft;
}
}
pii res;
if(!v[u]){res=find_centroids(u, total);}
else{
res={u, s};
}
v[s]=false;
return res;
}
vector<pii> k1, k2;
void path(int s, int l, int h, int tp){
if(l>k){
return;
}
if(tp==1){
k1.pb({l, h});
}
else{
k2.pb({l, h});
}
if(l==k){return;}
v[s]=true;
for(auto pr:g[s]){
int u=pr.ft, d=pr.sc;
if(!v[u]){
path(u, l+d, h+1, tp);
}
}
v[s]=false;
return;
}
void remove_edge(pii e, int d){
int u=e.ft, v=e.sc;
g[u].erase(find(g[u].begin(), g[u].end(),mp(v, d) ));
g[v].erase(find(g[v].begin(), g[v].end(),mp(u, d) ));
}
void combine(int d){
int i=k1.size()-1, j=0;
if( (k1.empty()) || (k2.empty()) ){return;}
sort(k1.begin(), k1.end());
sort(k2.begin(), k2.end());
while((i>=0) && (j<k2.size()) ){
while( ((k1[i].ft+k2[j].ft)<(k-d)) && (j<k2.size()) ){
j++;
}
if(j>=k2.size()){break;}
if( (k1[i].ft+k2[j].ft)==(k-d) ){
res=min(res, k1[i].sc+k2[j].sc);}
i--;
}
}
void subtask_4(){
queue<int> forest;
forest.push(1);
while(!forest.empty()){
int node=forest.front(); forest.pop();
build_sz(node);
//cout<<node<<"\n"<<flush;
if(sz[node]==1){continue;}
pii e=find_centroids(node, sz[node]);
int d=h[e];
//cout<<e.ft<<" "<<e.sc<<"\n"<<flush;
//partea din stanga:
k1.pb({0, 1});
v[e.sc]=true;v[e.ft]=false;
path(e.ft, 0, 1, 1); v[e.sc]=false;
//partea din dreapta:
k2.pb({0, 1});
v[e.ft]=true; v[e.sc]=false;
path(e.sc, 0, 1, 2); v[e.ft]=false;
//combinarea:
combine(d);
k1.clear();
k2.clear();
remove_edge(e, d);
forest.push(e.ft); forest.push(e.sc);
}
}
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 u=H[i][0]+1, v=H[i][1]+1, d=L[i];
g[u].pb({v, d}); g[v].pb({u, d});
h[{u, v} ]=d; h[{v, u} ]=d;
}
/*if( (k<=100) ){ subtask_3(1);}
else{
if(n<=1000){
for(int i=1; i<=n; i++){
res=min(res, subtask_2(i, 0, 1));
}
}
else{
subtask_4();
}
}*/
subtask_4();
if(res==(1e9)){
return -1;
}
return res-1;
}
