#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
int best_path(int N, int K, int H[][2], int L[]) {
vector<vll> adj; adj.resize(N);
vector<vlll> adjW; adjW.resize(N);
vector<bool> ignore; ignore.assign(N,0);
vll sz; sz.assign(N,0);
map<ll,vlll> mp;
ll ans = N+1;
RE(i,N-1) RE(j,2) adj [H[i][j]].push_back(H[i][!j]);
RE(i,N-1) RE(j,2) adjW[H[i][j]].push_back({H[i][!j], L[i]});
std::function<void(ll,ll)> dfsSize;
std::function<ll(ll,ll,ll)> dfsCentroid;
std::function<void(ll,ll,ll,ll,ll)> dfsMap;
std::function<void(ll)> centroidDecomp;
dfsSize = [&](ll u, ll p) {
sz[u] = 1;
FOR(v,adj[u]) {
if(ignore[v]) continue;
if(v == p) continue;
dfsSize(v,u);
sz[u] += sz[v];
}
};
dfsCentroid = [&](ll u, ll p, ll maxSize) {
FOR(v,adj[u]) {
if(ignore[v]) continue;
if(v == p) continue;
if(sz[v] > maxSize) return dfsCentroid(v,u,maxSize);
}
return u;
};
dfsMap = [&](ll u, ll p, ll root, ll len, ll depth) {
mp[depth].push_back({len,root});
FOR(v,adjW[u]) {
if(ignore[v.fi]) continue;
if(v.fi == p) continue;
dfsMap(v.fi,u,root,len+1,depth+v.se);
}
};
auto findCentroid = [&](ll u) {
dfsSize(u,-1);
return dfsCentroid(u,-1,sz[u]/2);
};
centroidDecomp = [&](ll u) {
ll cent = findCentroid(u);
mp.clear();
FOR(v,adjW[cent]) {
if(ignore[v.fi]) continue;
dfsMap(v.fi,cent,v.fi,1,v.se);
}
mp[0].push_back({0,-2});
FOR(p,mp) {
sort(all(p.se));
lll a={-1,-1}, b={-1,-1};
vlll newF;
FOR(np,p.se) {
if(a.se == np.se || b.se == np.se) continue;
if(a.fi == -1) {
a = np; newF.push_back(np);
} else if(b.fi == -1) {
b = np; newF.push_back(np);
}
}
p.se = newF;
}
FOR(p,mp) {
auto& f1 = p.se;
auto& f2 = mp[K - p.fi];
FOR(i,f1) FOR(j,f2) if(i.se != j.se) ans = min(ans, i.fi + j.fi);
}
// recursive
ignore[cent] = 1;
FOR(v,adj[cent]) {
if(ignore[v]) continue;
centroidDecomp(v);
}
};
centroidDecomp(0);
if(ans == N+1) ans = -1;
return ans;
}
