#include <bits/stdc++.h>
#include "race.h"
#define ve vector
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll, ll> pll;
const int MAXN = 1e6 + 10;
ll k;
ve<pll> g[MAXN];
map<ll, ll>* st[MAXN];
pll add[MAXN];
ll res;
void dfs(int v, int p){
pll mx = {-1, -1};
for(auto& to : g[v])
if(to.fi != p){
dfs(to.fi, v);
if(mx.fi == -1 || st[to.fi]->size() > st[mx.fi]->size())
mx = to;
}
if(mx.fi == -1){
st[v] = new map<ll, ll>();
st[v]->insert({0, 0});
return;
}
st[v] = st[mx.fi];
add[v] = add[mx.fi];
add[v].fi += mx.se;
add[v].se++;
for(auto& to : g[v])
if(to.fi != p && to != mx){
for(auto j : *st[to.fi]){
pll i = j;
i.fi += add[to.fi].fi;
i.se += add[to.se].se;
ll cur = (k - i.fi) - add[v].fi;
if(st[v]->find(cur) != st[v]->end())
res = min(res, (*st[v])[cur] + add[v].se + i.se + 1);
(*st[v])[i.fi - add[v].fi] = min((*st[v])[i.fi - add[v].fi], i.se - add[v].se);
}
}
for(auto& to : g[v])
if(to.fi != p)
(*st[v])[to.se - add[v].fi] = min((*st[v])[to.se - add[v].fi], 1 - add[v].se);
ll cur = k - add[v].fi;
if(st[v]->find(cur) != st[v]->end())
res = min(res, (*st[v])[cur] + add[v].se);
//cout << res << endl;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i = 0; i < N; i++){
g[i].clear();
delete(st[i]);
add[i] = {0, 0};
res = 1e18;
}
for(int i = 0; i < N - 1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0, 0);
for(auto i : *st[0])
cout << i.fi + add[0].fi << " " << i.se + add[0].se << endl;
return res == 1e18 ? -1 : res;
}
