#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const long long BIG = 1000000000000000000LL;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int borne = 201*1000;
const int lgb = 19;
int nbNoeuds, somVoulue;
vector<pii> adj[borne];
int anc[borne][lgb];
int se[borne][lgb];
// ROOT
int par[borne], dep[borne], dse[borne];
void dfsInit(int nod)
{
form2(i, 1, lgb) {
int tmp = anc[nod][i-1];
if (tmp == -1) anc[nod][i] = -1;
else {
anc[nod][i] = anc[tmp][i-1];
}
}
for (pii vor : adj[nod]) if (vor.fi != anc[nod][0]) {
int vo = vor.fi;
anc[vo][0] = nod;
dep[vo] = dep[nod] + 1;
dse[vo] = dse[nod] + vor.se;
dfsInit(vo);
}
}
int lca(int u, int v)
{
if (u == v) return u;
if (dep[u] < dep[v]) return lca(v, u);
ford(i, lgb) {
int kc = (1 << i);
if (dep[u] - dep[v] >= kc && anc[u][i] != -1) {
u = anc[u][i];
}
}
assert(dep[u] == dep[v]);
if (u == v) return u;
ford(i, lgb) {
int nu = anc[u][i], nv = anc[v][i];
if (nu != nv && nu != -1 && nv != -1) { u = nu; v = nv; }
}
assert(u != v);
assert(anc[u][0] == anc[v][0]);
return anc[u][0];
}
int nbEdges(int u, int v)
{
int art = lca(u, v);
int d1 = dep[u] - dep[art];
int d2 = dep[v] - dep[art];
assert(d1 >= 0 && d2 >= 0);
return d1+d2;
}
int sumEdges(int u, int v)
{
int art = lca(u, v);
int d1 = dse[u] - dse[art];
int d2 = dse[v] - dse[art];
assert(d1 >= 0 && d2 >= 0);
return d1+d2;
}
int solve()
{
anc[0][0] = -1;
dfsInit(0);
int rep = (int)(1e9);
form(i, nbNoeuds) form2(j, i+1, nbNoeuds) {
if (sumEdges(i,j) == somVoulue) {
chmin(rep, nbEdges(i, j));
}
}
if (rep == (int)(1e9)) rep = -1;
return rep;
}
int best_path(int N, int K, int H[][2], int L[])
{
nbNoeuds = N;
somVoulue = K;
form(i, N) {
int u = H[i][0], v = H[i][1];
int p = L[i];
adj[u].push_back({v,p});
adj[v].push_back({u,p});
}
return solve();
}
