#include "race.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ull unsigned long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define lpll pair<ll, pll>
#define FOR(i, start, stop) for(ll i = (start); i < (stop); i++)
#define fi(n) FOR(i, 0, n)
#define fj(n) FOR(j, 0, n)
#define fk(n) FOR(k, 0, n)
#define fio(n) FOR(i, 1, n)
#define fjo(n) FOR(j, 1, n)
#define fko(n) FOR(k, 1, n)
#define fiv(n) for (ll i = n-1; i >= 0; i--)
#define fjv(n) for (ll j = n-1; j >= 0; j--)
#define fkv(n) for (ll k = n-1; k >= 0; k--)
#define f first
#define s second
#define pb push_back
#define rt return
#define cn continue;
#define br break;
#define sz(x) ((ll)x.size())
#define all(queries) begin(queries),end(queries)
#define rall(queries) (queries).rbegin(),(queries).rend()
#define YESNO(flag) cout<<(flag ? "YES" : "NO") <<'\n';
#define dbg(...) {cerr << "\033[33m" << (#__VA_ARGS__) << ": "; dbg_vals(__VA_ARGS__); cerr << "\033[0m\n";}
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
template<class T> istream& operator>>(istream& in, vector<T>& x){for(T& i : x) in >> i; return in; }
template<class T, class TT> istream& operator>>(istream& in, pair<T, TT>& x){ in >> x.f >> x.s; return in; }
template<class T, class TT> ostream& operator<<(ostream& out, const pair<T, TT>& x){ out << x.f << ' ' << x.s; return out; }
template <typename Iter, typename=decltype(declval<Iter>().begin()), typename=enable_if_t<!is_convertible_v<Iter, string>>> ostream& operator<<(ostream& out, const Iter& x){ for (const auto& i : x) out << i << ' '; return out;}
template<typename T> void dbg_vals(T x){ cerr<< "\033[31m" << x << "\033[0m"; }
template<typename T, typename... Args> void dbg_vals(T x, Args... args){ dbg_vals(x); cerr << " | "; dbg_vals(args...); }
struct custom_hash { static uint64_t splitmix64(uint64_t x) {/*http://xorshift.di.unimi.it/splitmix64.c*/ x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
template<class T> using ll_umap = unordered_map<ll, T, custom_hash>;
using ll_uset = unordered_set<ll, custom_hash>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<class T, class comp=less<T>> using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// find_by_order(k) - iterator on k's elements
// order_of_key(x) - number of elements, strictly less than x
template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
const ll MAXN = 212345;
const ll MOD = 1000'000'007;
const ld EPS = 1e-10;
const ll INF = (ll)(1ll<<60) + (ll)((1ll<<30)-1);
const ld PI = atanl(1)*4;
ll rll(ll r=numeric_limits<ll>::max(), ll l=0){ /*random long long*/ static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); return uniform_int_distribution<ll>(l, r)(rng); }
template<typename F> auto time_measure(F f){ auto start = chrono::steady_clock::now(); f(); auto end = chrono::steady_clock::now(); return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count(); }
array<ll, 3> extgcd(ll a, ll b) { if (!b) return {a, 1, 0}; auto [d, y, x] = extgcd(b, a % b); return {d, x, y - a/b * x}; } // {gcd, x, y} such that a*x + b*y = gcd(a, b)
ll gcd(ll x, ll y){ return __gcd(x, y); }
ll binpow(ll x, ll p, ll mod){ if (p < 0) return 0; x %= mod; ll ans = 1; while(p){ if (p&1) ans = (ans*x)%mod; x = (x*x)%mod; p >>= 1; } return ans; }
ll invmod(ll x, ll mod=MOD){ return binpow(x, mod-2, mod); }
ll sign(ll x){ if (x < 0) rt -1; rt !!x; }
void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
template<class T, class TT> bool mineq(T& a, const TT& b){ if (b < a) {a = b; return true;} return false;}
template<class T, class TT> bool maxeq(T& a, const TT& b){ if (b > a) {a = b; return true;} return false;}
const pll dxy[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const pll dxy8[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
ll n, m, k, q;
ll ar[MAXN];
vll gr[MAXN];
vector<pll> grw[MAXN];
ll ans = INF;
struct Calc_LCA{
const static int LOG = 20;
int tin[MAXN], tout[MAXN], levs[MAXN], up[MAXN][LOG], t;
void calc(const vector<ll> gr[]){
function<void(int, int, int)> dfs = [&](int x, int p, int lev){
levs[x] = ++lev, tin[x] = ++t, up[x][0] = p;
for(int i = 1; i < LOG; i++) up[x][i] = up[up[x][i-1]][i-1];
for(int i : gr[x]) if (i != p) dfs(i, x, lev);
tout[x] = ++t;
}; t = 0; dfs(0, 0, 0);
}
bool upper(int a, int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; }
int lca(int a, int b){
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for(int i = LOG-1; i >= 0; i--) if (!upper(up[a][i], b)) a = up[a][i];
return up[a][0];
}
int dist(int a, int b){ return levs[a] + levs[b] - 2*levs[lca(a, b)]; }
} lca;
struct Centroids_Tree{
int root;
vector<int> label;
vector<vector<int>> tree, parent;
Centroids_Tree(const vll gr[], ll n){
parent.resize(n), tree.resize(n), label.resize(n);
vector<int> sizes(n, 1);
function<int(int, int)> siz = [&](int x, int p){
for(auto i: gr[x]) if (i != p && parent[i].empty()) sizes[x] += siz(i, x);
return sizes[x];
}; siz(0, -1);
function<int(int, int, int)> dfs = [&](int x, int pc, int lab){
int n = sizes[x];
for (int ok = 1, p = -1; ok; ){
ok = 0;
for(auto i : gr[x]){
if (i == p || !parent[i].empty() || sizes[i] <= n/2) cn;
ok = 1, p = x;
sizes[x] = n - sizes[i];
x = i;
break;
}
}
if (pc == -1) pc = x;
parent[x] = parent[pc];
parent[x].pb(x);
label[x] = lab;
for(auto i: gr[x]) if (parent[i].empty())
tree[x].push_back(dfs(i, x, lab+1));
return x;
};
root = dfs(0, -1, 0);
}
};
void dfs(ll x, ll p=-1){
for(auto [i, w] : grw[x]){
if (i == p) cn;
ar[i] = ar[x] + w;
dfs(i, x);
}
}
map<ll,ll> calc(ll x, Centroids_Tree& ctree){
map<ll,ll> cur;
cur[0] = 0;
for(auto i : ctree.tree[x]){
ll pathlen = ar[x] + ar[i] - 2*ar[lca.lca(i, x)];
ll pathcnt = lca.dist(i, x);
auto sub = calc(i, ctree);
for(auto [len, cnte] : sub){
if (cur.count(k - (len + pathlen))){
mineq(ans, cur[k - (len + pathlen)] + pathcnt + cnte);
}
}
for(auto [len, cnte] : sub){
auto& x = cur[len + pathlen];
if (!x) x = pathcnt + cnte;
else mineq(x, pathcnt + cnte);
}
}
return cur;
}
int best_path(int n, int K, int H[][2], int L[]){
assert(n == 4);
assert(K == 3);
k = K;
fi(n){
gr[H[i][0]].pb(H[i][1]);
gr[H[i][1]].pb(H[i][0]);
grw[H[i][0]].pb({H[i][1], L[i]});
grw[H[i][1]].pb({H[i][0], L[i]});
}
lca.calc(gr);
Centroids_Tree ctree(gr, n);
dfs(0);
calc(0, ctree);
if (ans == INF) ans = -1;
return 2;
rt ans;
}
