#include "race.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 28;
int k;
vector <pair<int, int>> g[MAX+2];
vector <int> st(MAX+2), is(MAX+2);
vector <pair<int, int>> dis;
map <int, int> mx;
int res=-1;
void dfs(int u, int c=-1) {
st[u] = 1;
for (auto &i : g[u]) {
if (i.ff == c || is[i.ff]) continue;
dfs(i.ff, u);
st[u] += st[i.ff];
}
}
int get(int u, int s, int c=-1) {
for (auto &i : g[u]) {
if (i.ff == c || is[i.ff]) continue;
if (st[i.ff] * 2 > s) return get(i.ff, s, u);
}
}
void dist(int u, int lv=0, int w=0, int c=-1) {
if (w <= k) dis.pb({w, lv});
for (auto &i : g[u]) {
if (i.ff == c || is[i.ff]) continue;
dist(i.ff, lv+1, w+i.ss, u);
}
}
void build(int u) {
dfs(u);
int c = get(u, st[u]);
is[c] = 1;
mx.clear();
for (auto &i : g[c]) {
dis.clear();
dist(i.ff, 1, i.ss);
for (auto &j : dis) {
if (mx.find(k-j.ff) == mx.end()) continue;
res = max(res, mx[k-j.ff] + j.ss);
}
for (auto &j : dis) {
mx[j.ff] = max(mx[j.ff], j.ss);
}
}
}
int best_path(int n, int K, int H[][2], int L[]) {
k = K;
build(1);
return res;
}
